BZOJ 3625 [Codeforces Round #250]小朋友和二叉树 多项式开根

题意:链接方法:多项式开根解析:首先先搞出来C(x)->即C的生成函数。然后推一下式子嘛选或者不选，，选的话是一个递归，不选是1。设F(x)为权值的生成函数。即然后搞一下。多项式求逆的条件是常数项有逆。所以那个加减我们就只能取减号而不能取加号然后乘以个共轭根式。现在考虑开根怎么求吧。假设我们要求故求逆O(nlogn)相乘O(nlogn)所以总复杂度T(n)=T(n/2)+O(nlogn)=O(nlogn).代码:using namespace std;typedef int ll;int n,m;ll c[N],Inv2,root_c[N],inv_root_c[N];int rev[N];x,ll y,ll MOD){long long ret=1;while(y){if(y&1)ret=(ret*x)%MOD;x=(x*x)%MOD;y>>=1;}return ret;}void NTT(ll *a,int n,int f){for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);for(int h=2;h<=n;h<<=1){ll wn=Quick_Power(3,(mod-1)/h,mod);for(int i=0;i<n;i+=h){ll w=1;for(int j=0;j<(h>>1);j++,w=(long long)w*wn%mod){ll t=(long long)a[i+j+(h>>1)]*w%mod;a[i+j+(h>>1)]=((a[i+j]-t)%mod+mod)%mod;a[i+j]=(a[i+j]+t)%mod;}}}if(f==-1){for(int i=1;i<(n>>1);i++)swap(a[i],a[n-i]);ll inv=Quick_Power(n,mod-2,mod);for(int i=0;i<n;i++)a[i]=(long long)a[i]*inv%mod;}}void Get_Inv(ll *a,ll *b,int n){static ll temp[N];if(n==1){b[0]=Quick_Power(a[0],mod-2,mod);return;}Get_Inv(a,b,n>>1);memcpy(temp,a,sizeof(a[0])*n);memset(temp+n,0,sizeof(a[0])*n);int m=n,L=0,nn=n;for(n=1;n<=m;n<<=1)L++;for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));NTT(temp,n,1),NTT(b,n,1);for(int i=0;i<n;i++)temp[i]=()temp[i]*b[i]%mod)%mod+mod)%mod)%mod;NTT(temp,n,-1);for(int i=0;i<(n>>1);i++)b[i]=temp[i];memset(b+nn,0,sizeof(b[0])*nn);n=nn;}void Get_Root(ll *a,ll *b,int n){static ll temp[N],inv_b[N];if(n==1){b[0]=1;return;}Get_Root(a,b,n>>1);memset(inv_b,0,sizeof(a[0])*n);Get_Inv(b,inv_b,n);memcpy(temp,a,sizeof(a[0])*n);memset(temp+n,0,sizeof(a[0])*n);int m=n,L=0,nn=n;for(n=1;n<=m;n<<=1)L++;for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));NTT(temp,n,1),NTT(b,n,1),NTT(inv_b,n,1);for(int i=0;i<n;i++)temp[i]=()inv_b[i]*temp[i]%mod)%mod)%mod;NTT(temp,n,-1);for(int i=0;i<(n>>1);i++)b[i]=temp[i];memset(b+nn,0,sizeof(b[0])*nn);n=nn;}int main(){scanf(“%d%d”,&n,&m);for(int i=1;i<=n;i++){ll x;scanf(“%d”,&x);c[x]++;}Inv2=Quick_Power(2,mod-2,mod);c[0]=((1-c[0])%mod+mod)%mod;for(int i=1;i<=100000;i++)c[i]=((-4*c[i])%mod+mod)%mod;int l;for(l=1;l<=m;l<<=1);Get_Root(c,root_c,l);root_c[0]=(1+root_c[0])%mod;Get_Inv(root_c,inv_root_c,l);for(int i=0;i<=100000;i++)inv_root_c[i]=((long long)2*inv_root_c[i])%mod;for(int i=1;i<=m;i++)printf(“%d\n”,inv_root_c[i]);}

一起吃早餐，午餐，晚餐。或许吃得不好，