Problem

Codeforces

Solution

写的时候被同学嘲讽：你现在才写这道题？

设 \(f_n\) 表示权值为 \(n\) 的二叉树的方案数，\(t_n\) 表示权值 \(n\) 的出现次数，则有
\[ f_n=\sum_{i=1}^nt_i\sum_{j=0}^{n-i} f_j f_{n-i-j} \]
这个式子可能还不够直观，写成下式：
\[ f_n=\sum_{i+j+k=n} t_if_jf_k \]
用生成函数表示，设 \(\{t_n\}\) 和 \(\{f_n\}\) 的 OGF 分别为 \(C(x),F(x)\) ，那么：\(F(x)=C(x)F(x)^2+1\)

解方程可得
\[ F(x)=\frac {1\pm\sqrt{1-4C(x)}} {2C(x)}=\frac {2} {1\pm \sqrt{1-C(x)}} \]
然而其中只有一个是对的，因为 \(F(0)=1\) ，而 \(\lim_\limits{x\to0} C(x)=0\)
\[ \lim_{x\to0}\frac {2} {1+ \sqrt{1-C(x)}}=1 \]

\[ \lim_{x\to0}\frac {2} {1- \sqrt{1-C(x)}}=\infty \]

当然了，极限的验证方法，更高级点可以用洛必达法则和泰勒展开，但涉及到了高等数学中的一些知识

这样我们只需要写多项式求逆和多项式开根即可。时间复杂度为 \(O(m\log m)\)。

Code

#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=300010,mod=998244353,G=3,inv2=499122177;
template <typename Tp> int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> void read(Tp &x)
{
    x=0;char ch=getchar();int f=0;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();
    if(f) x=-x;
}
int n,m,c[maxn],b[maxn],ans[maxn],rev[maxn];
int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x<y?x-y+mod:x-y;}
int power(int x,int y)
{
    int res=1;
    for(;y;y>>=1,x=(ll)x*x%mod)
      if(y&1)
        res=(ll)res*x%mod;
    return res;
}
void NTT(int *a,int N,int f)
{
    for(int i=1;i<N;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int i=1;i<N;i<<=1)
    {
        int gn=power(G,(mod-1)/(i<<1));
        for(int j=0;j<N;j+=(i<<1))
        {
            int g=1,x,y;
            for(int k=0;k<i;++k,g=(ll)g*gn%mod)
            {
                x=a[j+k];y=(ll)g*a[j+k+i]%mod;
                a[j+k]=pls(x,y);a[j+k+i]=dec(x,y);
            }
        }
    }
    if(f==-1)
    {
        int iv=power(N,mod-2);reverse(a+1,a+N);
        for(int i=0;i<N;i++) a[i]=(ll)a[i]*iv%mod;
    }
}
void getinv(int n,int *A,int *f)
{
    static int t[maxn];
    if(n==1){f[0]=power(A[0],mod-2);return ;}
    getinv((n+1)>>1,A,f);
    int N,l;
    for(N=1,l=0;N<(n<<1);N<<=1) ++l;
    for(int i=1;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    for(int i=0;i<n;i++) t[i]=A[i];
    for(int i=n;i<N;i++) t[i]=f[i]=0;
    NTT(t,N,1);NTT(f,N,1);
    for(int i=0;i<N;i++) f[i]=(ll)f[i]*dec(2,(ll)t[i]*f[i]%mod)%mod;
    NTT(f,N,-1);
    for(int i=n;i<N;i++) f[i]=0;
}
void getsqrt(int n,int *A,int *f)
{
    static int t[maxn],inv[maxn];
    if(n==1){f[0]=(A[0]==1?1:0);return ;}
    getsqrt((n+1)>>1,A,f);
    getinv(n,f,inv);
    int N,l;
    for(N=1,l=0;N<(n<<1);N<<=1) ++l;
    for(int i=1;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    for(int i=0;i<n;i++) t[i]=A[i];
    for(int i=n;i<N;i++) t[i]=0;
    NTT(t,N,1);NTT(f,N,1);NTT(inv,N,1);
    for(int i=0;i<N;i++) f[i]=(f[i]+(ll)t[i]*inv[i])%mod*inv2%mod;
    NTT(f,N,-1);
    for(int i=n;i<N;i++) f[i]=0;
}
int main()
{
    read(n);read(m);
    for(int i=1,x;i<=n;i++){read(x);c[x]=dec(c[x],4);}
    c[0]=pls(c[0],1);
    getsqrt(m+1,c,b);
    b[0]=pls(b[0],1);
    getinv(m+1,b,ans);
    for(int i=1;i<=m;i++) printf("%d\n",pls(ans[i],ans[i]));
    return 0;
}

CF438E The Child and Binary Tree

原文：https://www.cnblogs.com/totorato/p/11061192.html