[bzoj3625][Codeforces 250 E]The Child and Binary Tree（生成函數＋多項式運算＋FFT）

3625: [Codeforces Round #250]小朋友和二叉樹

Time Limit:?40 Sec??Memory Limit:?256 MB
Submit:?650??Solved:?283
[Submit][Status][Discuss]

Description

我們的小朋友很喜歡計算機科學，而且尤其喜歡二叉樹。
考慮一個含有n個互異正整數的序列c[1],c[2],...,c[n]。如果一棵帶點權的有根二叉樹滿足其所有頂點的權值都在集合{c[1],c[2],...,c[n]}中，我們的小朋友就會將其稱作神犇的。并且他認為，一棵帶點權的樹的權值，是其所有頂點權值的總和。
給出一個整數m，你能對于任意的s(1<=s<=m)計算出權值為s的神犇二叉樹的個數嗎？請參照樣例以更好的理解什么樣的兩棵二叉樹會被視為不同的。
我們只需要知道答案關于998244353(7*17*2^23+1,一個質數)取模后的值。

Input

第一行有2個整數 n,m(1<=n<=10^5; 1<=m<=10^5)。
第二行有n個用空格隔開的互異的整數 c[1],c[2],...,c[n]（1<=c[i]<=10^5)。

Output

輸出m行，每行有一個整數。第i行應當含有權值恰為i的神犇二叉樹的總數。請輸出答案關于998244353(=7*17*2^23+1,一個質數)取模后的結果。

Sample Input

樣例一：
2 3
1 2
樣例二：
3 10
9 4 3
樣例三：
5 10
13 10 6 4 15

Sample Output

樣例一：
1
3
9
樣例二：
0
0
1
1
0
2
4
2
6
15
樣例三：
0
0
0
1
0
1
0
2
0
5

HINT

?

對于第一個樣例，有9個權值恰好為3的神犇二叉樹：

?

Source

VFleaKing & pyx1997 感謝wyl8899提供中文翻譯

https://www.cnblogs.com/neighthorn/p/6497364.html

利用了二叉樹的遞歸定義，注意空樹情況要加一，因為生成函數的$x^0$為$0$，也就是默認了根節點必須有數。

剩下的就是多項式開根和逆元了。

#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std;

const int N=(1<<18)+100,P=998244353,g=3,inv2=(P+1)/2;
int n,x,m,c[N],a[N],f[N],t[N],ib[N],rev[N];

int ksm(ll a,int b){
   ll res;
   for (res=1; b; a=(a*a)%P,b>>=1)
      if (b & 1) res=res*a%P;
   return res;
}

void DFT(int a[],int n,int f){
   rep(i,0,n-1) if (i<rev[i]) swap(a[i],a[rev[i]]);
   for (int i=1; i<n; i<<=1){
      ll wn=ksm(g,(f==1) ? (P-1)/(i<<1) : (P-1)-(P-1)/(i<<1));
      for (int j=0,p=i<<1; j<n; j+=p){
         ll w=1;
         for (int k=0; k<i; k++,w=1ll*w*wn%P){
            int x=a[j+k],y=1ll*w*a[i+j+k]%P;
            a[j+k]=(x+y)%P; a[i+j+k]=(x-y+P)%P;
         }
      }
   }
   if (f==-1){
      int inv=ksm(n,P-2);
      rep(i,0,n-1) a[i]=1ll*a[i]*inv%P;
   }
}

void inverse(int a[],int b[],int l){
   if (l==1){ b[0]=ksm(a[0],P-2); return; }
   inverse(a,b,l>>1);
   int n=1,L=0; while (n<(l<<1))n<<=1,L++;
   rep(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
   rep(i,0,l-1) t[i]=a[i];
   rep(i,l,n-1) t[i]=0;
   DFT(t,n,1); DFT(b,n,1);
   rep(i,0,n-1) b[i]=1ll*b[i]*(2-1ll*t[i]*b[i]%P+P)%P;
   DFT(b,n,-1);
   rep(i,l,n-1) b[i]=0;
}

void Sqrt(int a[],int b[],int l){
   if (l==1) { b[0]=1; return; }
   Sqrt(a,b,l>>1);
   int n=1,L=0; while (n<(l<<1)) n<<=1,L++;
   rep(i,0,n-1) ib[i]=0;
   inverse(b,ib,l);
   rep(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
   rep(i,0,l-1) t[i]=a[i];
   rep(i,l,n-1) t[i]=0;
   DFT(t,n,1); DFT(b,n,1); DFT(ib,n,1);
   rep(i,0,n-1) b[i]=1ll*inv2*(b[i]+1ll*t[i]*ib[i]%P)%P;
   DFT(b,n,-1);
   rep(i,l,n-1) b[i]=0;
}

int main(){
   freopen("bzoj3625.in","r",stdin);
   freopen("bzoj3625.out","w",stdout);
   scanf("%d%d",&n,&m); c[0]=1;
   rep(i,1,n) scanf("%d",&x),c[x]-=4;
   rep(i,0,m) if (c[i]<0) c[i]+=P;
   int len=1; while (len<=m) len<<=1;
   Sqrt(c,a,len);
   a[0]++; if (a[0]>=P) a[0]-=P;
   inverse(a,f,len);
   rep(i,1,m) printf("%d\n",f[i]*2%P);
   return 0;
}

?