小朋友和二叉树

用生成函数的思想，其实这里就是FFT

考虑根节点放的数字，从而推出F的式子

有F=C*F*F+1

（其实这里可以分治NTT，复杂度相同（理论常数更小））

二元一次方程，求根公式

+的根，因为x->0的时候，f趋近于inf，舍弃

所以是-

再化简得到：

F=2/(1+sqrt(1-4C))

 

（顺便说一下：

一般实数域下，除法分为三种，一个是实数级别的，或者求余数，或者mod意义下得到一个数（这里没有实际意义，就是为了逆元做一个定义）

复数域下，除法可能只有共轭然后变成分子的乘法

多项式的话，要不然就是带余数的多项式除法，要不然就是分数线的形式，意义就是乘这个多项式的逆（除法就是一个表示，没有实际意义）

） 

 

多项式开根即可

代码：

#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*10+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=8*1e5+5;
const int mod=998244353;
const int G=3;
const int GI=332748118;
int n,m;
int c[N],d[N],e[N],t[N],co[N],p[N],ni[N],l[N];
int rev[N];
int inv2;
int qm(int x,int y){
int ret=1;
while(y){
if(y&1) ret=(ll)ret*x%mod;
x=(ll)x*x%mod;
y>>=1;
}
return ret;
}
int mo(int x){
return x>=mod?x-mod:x;
}
void NTT(int *f,int n,int c){
for(reg i=0;i<n;++i){
if(i>rev[i]){
f[i]^=f[rev[i]]^=f[i]^=f[rev[i]];
}
}
for(reg p=2;p<=n;p<<=1){
int gen;
if(c==1) gen=qm(G,(mod-1)/p);
else gen=qm(GI,(mod-1)/p);
for(reg l=0;l<n;l+=p){
int buf=1;
for(reg k=l;k<l+p/2;++k){
int tmp=(ll)buf*f[k+p/2]%mod;
f[k+p/2]=mo(f[k]-tmp+mod);
f[k]=mo(f[k]+tmp);
buf=(ll)buf*gen%mod;
}
}
}
}
void calc(int *f,int *g,int n){
for(reg i=0;i<n;++i){
rev[i]=rev[i>>1]>>1|((i&1)?n>>1:0);
}
NTT(f,n,1);NTT(g,n,1);
for(reg i=0;i<n;++i) f[i]=(ll)f[i]*g[i]%mod;
NTT(f,n,-1);
ll iv=qm(n,mod-2);
for(reg i=0;i<n;++i) f[i]=(ll)f[i]*iv%mod;
}
void inv(int *f,int *g,int n){//mod n
if(n==1){
g[0]=qm(f[0],mod-2);return;
}
inv(f,g,n>>1);
for(reg i=0;i<n/2;++i) d[i]=g[i],e[i]=f[i];
for(reg i=n/2;i<=n;++i) d[i]=0,e[i]=f[i];
for(reg i=n+1;i<=2*n;++i) d[i]=0,e[i]=0;
for(reg i=0;i<2*n;++i){
rev[i]=rev[i>>1]>>1|((i&1)?(2*n)>>1:0);
}
NTT(d,2*n,1);NTT(e,2*n,1);
for(reg i=0;i<2*n;++i){
g[i]=mo(mo(2*d[i])-(ll)e[i]*d[i]%mod*d[i]%mod+mod);
}
NTT(g,2*n,-1);
ll iv=qm(2*n,mod-2);
for(reg i=0;i<2*n;++i){
if(i<n) g[i]=(ll)g[i]*iv%mod;
else g[i]=0;
}
}
void sqr(int *f,int *g,int n){
if(n==1){
g[0]=1;return;
}
sqr(f,g,n>>1);
for(reg i=0;i<n/2;++i) co[i]=(ll)g[i]%mod,l[i]=g[i],p[i]=f[i],ni[i]=0;
for(reg i=n/2;i<n;++i) co[i]=0,l[i]=0,p[i]=f[i],ni[i]=0;
for(reg i=n;i<2*n;++i) co[i]=0,l[i]=0,p[i]=0,ni[i]=0;
memset(ni,0,sizeof ni);
inv(co,ni,n);
calc(p,ni,2*n);
for(reg i=0;i<2*n;++i){
if(i<n) g[i]=((ll)g[i]+p[i])%mod*inv2%mod;
else g[i]=0;
}
}
int main(){
rd(n);rd(m);
inv2=qm(2,mod-2);
int lp=max(n,m);
int x;
for(reg i=1;i<=n;++i){
rd(x);c[x]=1;
lp=max(lp,x);
}
int len=1;
for(;len<=lp;len<<=1);
for(reg i=0;i<len;++i){
c[i]=-4*c[i]+mod;
}
c[0]++;
//
cout<<" len len "<<len<<endl;

sqr(c,t,len);
//
cout<<" sqrt "<<endl;
//
for(reg i=0;i<len;++i){
//
cout<<t[i]<<" ";
//
}cout<<endl;
t[0]=(t[0]+1)%mod;
memset(ni,0,sizeof ni);
inv(t,ni,len);
for(reg i=1;i<=m;++i){
ll ans=2*ni[i]%mod;
printf("%lldn",ans);
}
return 0;
}
}
signed main(){
Miracle::main();
return 0;
}
/*
Author: *Miracle*
Date: 2019/1/28 20:07:14
*/

其实就是列出式子

然后推式子

 

不用分治NTT的话，

生成函数这里主要是：F=C*F*F+1的整体思想

也可以看做多项式优化DP系列