T666848 闪现树题解

出的很好的计数题。

我们的最初想法是，发现只会向下延伸

2

或

3

个儿子。设

f_i,g_i

表示第

i

层有几个节点 将要（在下一层） 向下延伸

3

个，有几个 将要（在下一层） 向下延伸

2

个。

那么

f_i=2g_{i-1}+f_{i-1}

且

g_i=2f_{i-1}

。

发现当

n\le dep

时，

f_i

会多算一些节点，因为有些不能额外延伸了（它这个点的“延伸路径”已经等于

n

了，不能再往下扩了）。

考察这些“不能延伸”的节点的性质，发现：

对于一个往下延伸

3

个儿子的点，我们发现它一定来自于如下路径：

1

阶闪现树的左右叶子

+1

阶闪现树的中叶子

+1

阶闪现树的左右叶子+...注意这里等价于用一个类似

+1,+2,+2,+1,....

的，长度为

n

的序列描述它的

dep

（就是

dep=1+2+2+1+....

）。我们整体把它

-1

，最后加回来，中间用组合意义计算即可。最后，发现

dep

层的“将要（在下一层） 不能向下延伸

3

个儿子”的冗余节点的个数为

4^{dep-n}\times \binom{n}{dep-n}

。

然后每一层节点个数就是

f_i,g_i

，注意在减去冗余节点之前计算。实现时注意取模。

CPP

#include<bits/stdc++.h>
#define _for(i,x,y) for(int i=x;i<=y;++i)
#define _forp(i,x,y,z) for(int i=x;i<=y;i+=z)
#define _rep(i,x,y) for(int i=x;i<y;++i)
using namespace std;

const int N=10000005,mod=998244353;

int ans=0,f[N],fac[N],inv[N],pow4[N],g[N],n,l,r;

int qpow(int x,int y){
	if(y<0) return 0;
	int ans=1;
	x%=mod; 
	while(y){
		if(y&1) ans=1ll*ans*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ans;
}

int C(int n,int m){
	if(n==m) return 1;
	if(m==0) return 1;
	if(n<m) return 0;
	if(m<0) return 0;
	return 1ll*fac[n]*inv[n-m]%mod*inv[m]%mod;
}

void build(){
	fac[0]=pow4[0]=1;
	_for(i,1,N-5) fac[i]=1ll*fac[i-1]*i%mod,pow4[i]=1ll*pow4[i-1]*4ll%mod;;
	inv[N-5]=qpow(fac[N-5],mod-2);
	for(int i=N-6;i;--i) inv[i]=1ll*inv[i+1]*(i+1ll)%mod ;
}

void solve(){
	cin>>n>>l>>r;
	build();
	f[0]=1; 
	g[0]=0; 
	_for(i,1,min(N-5,2*n)){
		g[i]=f[i-1]*2%mod;
		f[i]=(g[i-1]*2%mod+f[i-1])%mod; 
		if(l<=i&&i<=r){
			ans^=(f[i]+g[i])%mod;
		}
		if(i>=n) f[i]-=(1ll*pow4[i-n]*C(n,i-n))%mod,f[i]+=mod,f[i]%=mod;
	}
	cout<<ans<<'\n';
}
signed main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
	int T=1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

T666848 闪现树题解

文章操作

相关推荐

评论

T666848 闪现树题解