题意:
给出一个大小为n的集合C;
对于i=1…m计算有多少二叉树满足每个节点的权值都在集合C中且所有结点权值和为i;
对998244353取模,左右儿子有别;
此题也是CodeF
题解:
生成函数系列题解之三?
这题先对C搞个生成函数吧,令其为C(x);
而我们要求的是树的计数的函数F(x);
列一下方程,F(x)=C(x)*F^2(x)+1;
F^2(x)表示它的左右儿子的方案,,C(x)是限制它自己的权值,+1是因为空树有一个常数项;
这个方程式很有道理的,不理解就在理解一下;
然后解一下二次方程。。。
解多项式方程?
上求根公式,F(x)=(1±√ 1-4C(x))/2C(x);
二次方程可能有两个解,但是这个方程只有一个;
因为显然C(x)无常数项,开根之后出来有一个1,而分母又没有常数项;
只有取减号时将常数项减掉才能做除法;
多项式开根的具体方法还是倍增;
过程中每一层都要常数次调用FFT和多项式求逆;
时间复杂度?T(n)=O(nlogn)+T(n/2)=O(nlogn);
这个复杂度简直毒瘤。。。至于原因。。。这个复杂度支持各种嵌套。。;
树套树都不能无限套而这东西简直可怕;
代码:
#include<math.h>#include<stdio.h>#include<string.h>#include<algorithm>#define N 261244<<1using namespace std;typedef long long ll;const int mod=998244353;const int div2=499122177;int a[N],b[N],c[N];int pow(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;}void NTT(int *a,int len,int type){int i,j,t,h;for(i=0,t=0;i<len;i++){if(i>t)swap(a[i],a[t]);for(j=(len>>1);(t^=j)<j;j>>=1);}for(h=2;h<=len;h<<=1){int wn=pow(5,(mod-1)/h);for(i=0;i<len;i+=h){int w=1;for(j=0;j<(h>>1);j++,w=(ll)w*wn%mod){int temp=(ll)w*a[i+j+(h>>1)]%mod;a[i+j+(h>>1)]=(a[i+j]-temp+mod)%mod;a[i+j]=(a[i+j]+temp)%mod;}}}if(type==-1){for(i=1;i<(len>>1);i++)swap(a[i],a[len-i]);int inv=pow(len,mod-2);for(i=0;i<len;i++)a[i]=(ll)a[i]*inv%mod;}}void inv(int *a,int *b,int len){if(len==1){b[0]=pow(a[0],mod-2);return ;}inv(a,b,len>>1);static int temp[N];memcpy(temp,a,sizeof(int)*len);memset(temp+len,0,sizeof(int)*len);NTT(temp,len<<1,1),NTT(b,len<<1,1);for(int i=0;i<len<<1;i++)b[i]=(ll)b[i]*(2-(ll)temp[i]*b[i]%mod+mod)%mod;NTT(b,len<<1,-1);memset(b+len,0,sizeof(ll)*len);}void sqrt(int *a,int *b,int len){static int tempa[N],tempb[N];if(len==1){b[0]=1;return ;}sqrt(a,b,len>>1);memset(tempb,0,sizeof(int)*len);memset(tempb+len,0,sizeof(int)*len);inv(b,tempb,len);memcpy(tempa,a,sizeof(int)*len);memset(tempa+len,0,sizeof(int)*len);NTT(tempa,len<<1,1),NTT(b,len<<1,1),NTT(tempb,len<<1,1);for(int i=0;i<len<<1;i++)b[i]=(ll)(b[i]+(ll)tempa[i]*tempb[i]%mod)%mod*div2%mod;NTT(b,len<<1,-1);memset(b+len,0,sizeof(int)*len);}int main(){int n,m,i,j,k,len;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d",&k);if(k<=m)a[k]++;}for(i=1<<30;i;i>>=1)if(m&i){len=i<<1;break;}for(i=0;i<len;i++)if(a[i])a[i]=mod-4;a[0]++;sqrt(a,b,len);memcpy(a,b,sizeof(int)*len);a[0]++;memset(b,0,sizeof(int)*len);inv(a,b,len);memcpy(a,b,sizeof(int)*len);for(i=1;i<=m;i++)printf("%d\n",(a[i]+a[i])%mod);return 0;}
要知道,当你一直在担心错过了什么的时候,