T666848 闪现树题解

Xiphi · 2025-09-13 22:30:05 · 个人记录

出的很好的计数题。

我们的最初想法是，发现只会向下延伸 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，注意在减去冗余节点之前计算。实现时注意取模。

#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 闪现树题解