题解 CF438E 【The Child and Binary Tree】

都是多项式开根啊……虽然可以理解 不过我非常喜欢分治fft所以我用分治fft过了这题 __________________ ### 前置芝士：快速傅里叶变换/快速数论变换(ftt/ntt) 那个……如果不会多项式的基础芝士的话还是出门左转你站模板区去学习一下好了 ## 本题题解 那么我们先来推一下dp式子不然我们做不了这题…… 我们设$f(n)$表示权值恰好为n的二叉树的个数，设$c(i)$表示i这种权值是否出现 接下来我们的转移就十分的简单粗暴了，我们枚举根的权值是什么，这样我们就可以得到这样一个柿子 $$f(n)=\sum_{i+j=n}c(i)g(j),f(0)=1$$ 等一下，g是什么呢？ 我们发现我们枚举完根的权值之后还剩下一些权值分给左右儿子,由于左子树和右子树是两颗树，因此我们不能简单的递归到f来解决问题，所以我们设了一个中转数组g来解决问题，我们令$g(n)$表示权值和恰好为n的有序二叉树对的个数，或者说，我们令g表示这个式子 $$g(n)=\sum_{i+j=n}f(i)f(j),g(0)=1$$ 然后这又有什么用呢? 似乎我们推出来的式子和普通的分治fft式子相去甚远。 我们推出来的式子似乎是一个**我 卷 我 自 己**的形式，或者更加准确点，f和g这两个数组在左右互搏……，看起来此时我们似乎不能使用传统的分治fft来解决这个问题了…… 但是事实上这种式子分治fft还是能做的，因为分治fft本质上是一个cdq分治，因此我们依然可以使用cdq分治的思想解决这个问题 再具体点来讲我们依然使用cdq分治的老套路，考虑左侧询问对右侧询问的贡献 当然前提是我们递归下去了左半边，这样的话我们可以假设左侧的f和g是全部求好的 假设我们正在分治区间$[l,r)$，左侧区间是$[l,mid)$右侧区间是$[mid,r)$ 接下我们希望求出左侧区间对于右侧区间中一个点n的贡献，换句话说，我们希望计算这个式子 $$\sum_{i+j=n}c(i)g(j)$$ 并且满足一个限制条件是i和j至少有一个落在$[l,mid)$这个区间当中 那么我们把这个贡献拆成三部分来计算，第一部分是i和j都落在$[l,mid)$这个区间时对答案的贡献，也就是让我们求出这个式子 $$\sum_{i=l}^{mid-1}c(i)\sum_{j=l}^{mid}g(j)[i+j=n]$$ 然后我们令$c'(i)=c(i-l),g'(j)=g(j-l)$我们会得到这样一个神奇的式子 $$\sum_{i=0}^{mid-l-1}c'(i)\sum_{j=0}^{mid-l-1}g'(j)[i+j=n-2l]$$ 那么我们只需要对$c',g'$做一遍卷积就可以计算出这一部分的贡献了，此时我们的卷积的序列长度是分治区间长度级别的所以复杂度依然是对的 接下来我们考虑i落在这个区间而j不落在这个区间的贡献，它是这个式子 $$\sum_{i=l}^{mid-1}c(i)\sum_{j=0}^{l-1}g(j)[i+j=n]$$ 当然此时我们依然用$c'$来代换$c$所以我们可以得到这个式子 $$\sum_{i=0}^{mid-1}c(i)\sum_{j=0}^{l-1}g(j)[i+j=n-l]$$ 我们注意到一件事情是$n$是在$(mid,n]$这个区间内的，所以$n-l$的值不会超过$r-l$也就是当前分治区间的长度,所以对于g这个多项式，我们仅仅需要保留前$(r-l)$项 此时我们将$c'$和$g$卷出来依然可以正确的推出这一部分的贡献，并且我们此时卷积的序列长度依然是分治区间长度级别的，所以我们的复杂度依然是对的 对于第三部分的贡献也就是i不落在左侧区间而j落在左侧区间的贡献，计算方法和上面一致，我们用$g'$卷上保留前$(r-l)$系数的c多项式就可以轻松计算出这部分的贡献了 那么我们计算完左侧c和g对右侧f的贡献之后我们还需要计算左侧f对右侧g的贡献 这个部分和刚才的推导方式差不多，都是分情况讨论3种不同情况的贡献，不过这里有一个好处就是第二种贡献和第3种贡献的权值相等，因此可以只做一遍卷积然后把权值乘2就可以计算了 如此这般我们就将每一层的卷积长度控制在了分治区间长度级别 所以我们的复杂度就是$T(n)=2T(n/2)+O(nlogn)=O(nlog^2n)$了 这样的话我们就成功通过cdq分治处理出了f数组，然后我们就可以通过这道题啦~ 注意一件事情是当分治区间长度是1的时候我们需要特殊处理一下c对f的贡献和f对g的贡献，这个自己手动加上就行了 然后听起来这东西挺麻烦其实代码并不长…… 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=262144+10;typedef unsigned long long ll;const ll mod=998244353; inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;} int rv[22][N];ll rt[2][22];int n;int m; inline void pre()//简易的ntt板子 { for(int i=1;i<=18;i++) for(int j=1;j<(1<<i);j++)rv[i][j]=(rv[i][j>>1]>>1)|((j&1)<<(i-1)); for(int i=1,t=(mod-1)/2;i<=20;t>>=1,i++)rt[0][i]=po(3,t); for(int i=1,t=(mod-1)/2;i<=20;t>>=1,i++)rt[1][i]=po(332748118,t); } # define md(x) (x=((x>mod)?x-mod:x)) inline void ntt(ll* a,int len,int d,int o) { for(int i=0;i<len;i++)if(i<rv[d][i])swap(a[rv[d][i]],a[i]); for(int k=1,j=1;k<len;k<<=1,j++) for(int s=0;s<len;s+=(k<<1)) for(int i=s,w=1;i<s+k;i++,w=w*rt[o][j]%mod) {ll a1=a[i+k]*w%mod;a[i+k]=a[i]+mod-a1;md(a[i+k]);a[i]+=a1;md(a[i]);} if(o){ll iv=po(len,mod-2);for(int i=0;i<len;i++)(a[i]*=iv)%=mod;} }ll f[N];ll g[N];ll c[N];ll tr1[N];ll tr2[N];ll tr3[N]; ll tf[20][N];ll tg[20][N];ll tc[20][N];ll ck[N];ll bru[N]; inline void solve(int l,int r,int k)//分治fft { if(r-l==1){f[0]=1;g[0]=1;(f[l]+=c[l])%=mod;(g[l]+=f[l]*2)%=mod;return;} int mid=(l+r)/2;solve(l,mid,k-1); for(int i=l;i<mid;i++)tr1[i-l]=c[i];for(int i=(1<<(k-1));i<(1<<(k+1));i++)tr1[i]=0; for(int i=l;i<mid;i++)tr2[i-l]=g[i];for(int i=(1<<(k-1));i<(1<<(k+1));i++)tr2[i]=0; ntt(tr1,(1<<(k+1)),k+1,0);ntt(tr2,(1<<(k+1)),k+1,0);//左侧对右侧的贡献 for(int i=0;i<(1<<(k+1));i++)tr3[i]=tr1[i]*tr2[i]%mod;ntt(tr3,(1<<(k+1)),k+1,1); for(int i=max(mid,(l<<1));i<r;i++)(f[i]+=tr3[i-(l<<1)])%=mod; for(int i=0;i<(1<<(k+1));i++)tr3[i]=tr1[i]*tg[k][i]%mod;ntt(tr3,(1<<(k+1)),k+1,1); for(int i=mid;i<r;i++)(f[i]+=tr3[i-l])%=mod; for(int i=0;i<(1<<(k+1));i++)tr3[i]=tr2[i]*tc[k][i]%mod;ntt(tr3,(1<<(k+1)),k+1,1); for(int i=mid;i<r;i++)(f[i]+=tr3[i-l])%=mod; for(int i=l;i<mid;i++)tr1[i-l]=f[i];for(int i=(1<<(k-1));i<(1<<(k+1));i++)tr1[i]=0; ntt(tr1,(1<<(k+1)),k+1,0); for(int i=0;i<(1<<(k+1));i++)tr3[i]=tr1[i]*tr1[i]%mod;ntt(tr3,(1<<(k+1)),k+1,1); for(int i=max(mid,(l<<1));i<r;i++)(g[i]+=tr3[i-(l<<1)])%=mod; for(int i=0;i<(1<<(k+1));i++)tr3[i]=tr1[i]*tf[k][i]%mod;ntt(tr3,(1<<(k+1)),k+1,1); for(int i=mid;i<r;i++)(g[i]+=2*tr3[i-l])%=mod;solve(mid,r,k-1); if(l==0) { for(int i=0;i<r;i++)tf[k][i]=f[i];ntt(tf[k],(1<<(k+1)),k+1,0); for(int i=0;i<r;i++)tg[k][i]=g[i];ntt(tg[k],(1<<(k+1)),k+1,0); for(int i=0;i<r;i++)tc[k][i]=c[i];ntt(tc[k],(1<<(k+1)),k+1,0); } } int main() { pre();scanf("%d%d",&n,&m);for(int i=1,t;i<=n;i++)scanf("%d",&t),c[t]=1; solve(0,131072,17);for(int i=1;i<=m;i++)printf("%I64d\n",f[i]);return 0;//拜拜程序~ } ```