Problem
Solution
写的时候被同学嘲讽：你现在才写这道题？
设 (f_n) 表示权值为 (n) 的二叉树的方案数，(t_n) 表示权值 (n) 的出现次数，则有
[f_n=sum_{i=1}^nt_isum_{j=0}^{n-i} f_j f_{n-i-j}
]
这个式子可能还不够直观，写成下式：
[f_n=sum_{i+j+k=n} t_if_jf_k
]
用生成函数表示，设 ({t_n}) 和 ({f_n}) 的 OGF 分别为 (C(x),F(x)) ，那么：(F(x)=C(x)F(x)^2+1)
解方程可得
[F(x)=frac {1pmsqrt{1-4C(x)}} {2C(x)}=frac {2} {1pm sqrt{1-C(x)}}
]
然而其中只有一个是对的，因为 (F(0)=1) ，而 (lim_limits{x o0} C(x)=0)
[lim_{x o0}frac {2} {1+ sqrt{1-C(x)}}=1
]
[lim_{x o0}frac {2} {1- sqrt{1-C(x)}}=infty
]
当然了，极限的验证方法，更高级点可以用洛必达法则和泰勒展开，但涉及到了高等数学中的一些知识
这样我们只需要写多项式求逆和多项式开根即可。时间复杂度为 (O(mlog m))。
Code
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=300010,mod=998244353,G=3,inv2=499122177;
template <typename Tp> int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> void read(Tp &x)
{
x=0;char ch=getchar();int f=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();
if(f) x=-x;
}
int n,m,c[maxn],b[maxn],ans[maxn],rev[maxn];
int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x<y?x-y+mod:x-y;}
int power(int x,int y)
{
int res=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1)
res=(ll)res*x%mod;
return res;
}
void NTT(int *a,int N,int f)
{
for(int i=1;i<N;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int i=1;i<N;i<<=1)
{
int gn=power(G,(mod-1)/(i<<1));
for(int j=0;j<N;j+=(i<<1))
{
int g=1,x,y;
for(int k=0;k<i;++k,g=(ll)g*gn%mod)
{
x=a[j+k];y=(ll)g*a[j+k+i]%mod;
a[j+k]=pls(x,y);a[j+k+i]=dec(x,y);
}
}
}
if(f==-1)
{
int iv=power(N,mod-2);reverse(a+1,a+N);
for(int i=0;i<N;i++) a[i]=(ll)a[i]*iv%mod;
}
}
void getinv(int n,int *A,int *f)
{
static int t[maxn];
if(n==1){f[0]=power(A[0],mod-2);return ;}
getinv((n+1)>>1,A,f);
int N,l;
for(N=1,l=0;N<(n<<1);N<<=1) ++l;
for(int i=1;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
for(int i=0;i<n;i++) t[i]=A[i];
for(int i=n;i<N;i++) t[i]=f[i]=0;
NTT(t,N,1);NTT(f,N,1);
for(int i=0;i<N;i++) f[i]=(ll)f[i]*dec(2,(ll)t[i]*f[i]%mod)%mod;
NTT(f,N,-1);
for(int i=n;i<N;i++) f[i]=0;
}
void getsqrt(int n,int *A,int *f)
{
static int t[maxn],inv[maxn];
if(n==1){f[0]=(A[0]==1?1:0);return ;}
getsqrt((n+1)>>1,A,f);
getinv(n,f,inv);
int N,l;
for(N=1,l=0;N<(n<<1);N<<=1) ++l;
for(int i=1;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
for(int i=0;i<n;i++) t[i]=A[i];
for(int i=n;i<N;i++) t[i]=0;
NTT(t,N,1);NTT(f,N,1);NTT(inv,N,1);
for(int i=0;i<N;i++) f[i]=(f[i]+(ll)t[i]*inv[i])%mod*inv2%mod;
NTT(f,N,-1);
for(int i=n;i<N;i++) f[i]=0;
}
int main()
{
read(n);read(m);
for(int i=1,x;i<=n;i++){read(x);c[x]=dec(c[x],4);}
c[0]=pls(c[0],1);
getsqrt(m+1,c,b);
b[0]=pls(b[0],1);
getinv(m+1,b,ans);
for(int i=1;i<=m;i++) printf("%d
",pls(ans[i],ans[i]));
return 0;
}