CF438E The Child and Binary Tree

╰+哭是因爲堅強的太久メ 2021-11-02 14:12 188阅读 0赞

# 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;
    }

转载于:https://www.cnblogs.com/totorato/p/11061192.html

[Codeforces]: https://codeforces.com/problemset/problem/438/E