LOJ6684

发表于 | 分类于

无标号“奇树”计数。

原问题就是在问：黑白染色的树，叶子都是黑色，同色点不允许连边。无标号意义下含有$n$个黑点的黑根树的个数。

假设白根树个数为$f_n$，黑根树为$g_n$，很容易列出下面的式子:

随手化简一下：

那么就可以分治$NTT$求解了，复杂度$O(nlog^2n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define re register
#define I inline int
#define V inline void
#define ll long long int
#define FOR(i,a,b) for(re int i=a;i<=b;i++)
#define ROF(i,a,b) for(re int i=a;i>=b;i--)
const int N=1<<19|1,mod=998244353,inv2=mod+1>>1;
int n,m,ans;
int f[N],g[N],h[N],X[N],Y[N],fa[N],ga[N];
I Pow(ll t,int x){
    re ll s=1;
    while(x){
        if(x&1)s=s*t%mod;
        t=t*t%mod,x>>=1;
    }
    return s;
}
int lmt=1,w[N],r[N];
V init(){
    int l=0;n<<=1;
    while(lmt<=n)lmt<<=1,++l;
    FOR(i,1,lmt-1)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    int wn=Pow(3,(mod-1)>>l);w[lmt>>1]=1;
    FOR(i,(lmt>>1)+1,lmt-1)w[i]=(ll)w[i-1]*wn%mod;
    ROF(i,(lmt>>1)-1,1)w[i]=w[i<<1];
    lmt=__builtin_ctz(lmt),n>>=1;
}
I getLen(int n){return 1<<(32-__builtin_clz(n));}
V DFT(int*a,int l){
    static unsigned long long int tmp[N];
    re int u(lmt-__builtin_ctz(l)),t;
    FOR(i,0,l-1)tmp[i]=a[r[i]>>u];
    for(re int i=1;i<l;i<<=1)
        for(re int j=0,step=i<<1;j<l;j+=step)
            FOR(k,0,i-1)
                t=tmp[i+j+k]*w[i+k]%mod,tmp[i+j+k]=tmp[j+k]+mod-t,tmp[j+k]+=t;
    FOR(i,0,l-1)a[i]=tmp[i]%mod;
}
V IDFT(int*a,int l){
    reverse(a+1,a+l),DFT(a,l);
    re int bk(mod-(mod-1)/l);
    FOR(i,0,l-1)a[i]=(ll)a[i]*bk%mod;
}
I get_len(int l){return 1<<(32-__builtin_clz(l));}
V init(const int&x){
    if(x^1){
        g[x]=1ll*g[x]*Pow(x-1,mod-2)%mod;
        f[x]=(1ll*x*g[x]+ga[x]+f[x])%mod;
        f[x]=1ll*f[x]*Pow(x,mod-2)%mod;
    }
    else f[x]=g[x]=1;
    for(re int j=x,t=1ll*f[x]*x%mod;j<=n;j+=x)fa[j]=(fa[j]+t)%mod;
    for(re int j=x,t=1ll*g[x]*x%mod;j<=n;j+=x)ga[j]=(ga[j]+t)%mod;
}
V mul(int l){
    DFT(X,l),DFT(Y,l);
    FOR(i,0,l-1)X[i]=1ll*X[i]*Y[i]%mod;
    IDFT(X,l);
}
V cl(int l){memset(X,0,l<<2),memset(Y,0,l<<2);}
V cdq(int L,int R){
    if(L==R)return init(L);
    re int mid=L+R>>1,l;
    cdq(L,mid);
    if(L==1){
        l=get_len(R-L);
        FOR(i,L,mid)X[i-L]=f[i],Y[i-L]=ga[i];mul(l);
        FOR(i,mid+1,R)f[i]=(f[i]+X[i-L-1])%mod;cl(l);
        FOR(i,L,mid)X[i-L]=g[i],Y[i-L]=fa[i];mul(l);
        FOR(i,mid+1,R)g[i]=(g[i]+X[i-L-1])%mod;cl(l);
    }
    else{
        l=get_len(R+mid-L-L+1);
        FOR(i,L,mid)X[i-L]=f[i];
        FOR(i,1,R-L)Y[i-1]=ga[i];mul(l);
        FOR(i,mid+1,R)f[i]=(f[i]+X[i-L-1])%mod;cl(l);
        FOR(i,L,mid)X[i-L]=ga[i];
        FOR(i,1,R-L)Y[i-1]=f[i];mul(l);
        FOR(i,mid+1,R)f[i]=(f[i]+X[i-L-1])%mod;cl(l);
        FOR(i,L,mid)X[i-L]=g[i];
        FOR(i,1,R-L)Y[i-1]=fa[i];mul(l);
        FOR(i,mid+1,R)g[i]=(g[i]+X[i-L-1])%mod;cl(l);
        FOR(i,L,mid)X[i-L]=fa[i];
        FOR(i,1,R-L)Y[i-1]=g[i];mul(l);
        FOR(i,mid+1,R)g[i]=(g[i]+X[i-L-1])%mod;cl(l);
    }
    cdq(mid+1,R);
}
int main(){
    cin>>n,m=n,n=get_len(n),init(),cdq(1,n),n=m;
    FOR(i,1,n)std::cout<<g[i]<<'\n';
    return 0;
}