Qiuly

「Codeforces Round #250」小朋友和二叉树 多项式开根+多项式求逆 bzoj3625
考虑 $dp$ ,设 $f_x$ 表示权值和为 $x$ 的树的个数,接着设 $C_x$ 表示 $x$ 这个权值是否...
扫描右侧二维码阅读全文
18
2019/09

「Codeforces Round #250」小朋友和二叉树 多项式开根+多项式求逆 bzoj3625

考虑 $dp$ ,设 $f_x$ 表示权值和为 $x$ 的树的个数,接着设 $C_x$ 表示 $x$ 这个权值是否可用。很显然可以得到转移柿:

$$ f_{x+y+a}=f_{x}f_{y}+C_{a}+1 $$

后面的 $+1$ 是空树情况。

将 $f,C$ 看作生成函数,那么很显然:

$$ f=f^2C+1 $$

解方程即可,通过小学奥数我们可以得到:

$$ x=\frac{-b±\sqrt{b^2-4ac}}{2a}\\ f=\frac{1±\sqrt{1-4C}}{2C} $$

上下同时乘上 $1∓\sqrt{1-4C}$ :

$$ f=\frac{2}{1+\sqrt{1-4C}} $$

这里省去了分子取 $+$ 的情况,因为这样可能会使得分母变成 $0$ 。

对于上面的柿子,直接多项式开根$+$多项式求逆即可。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=4e5+2;
const ll mod=998244353;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Poly {
    int flip[N],A[N],B[N],C[N],D[N];
    inline int pow(int x,int y) {
        int res=1;x%=mod;
        for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) res=1ll*res*x%mod;
        return res;
    }
    inline void NTT(int*f,int limit,short inv) {
        for(int i=0;i<limit;++i)
            if(i<flip[i]) swap(f[i],f[flip[i]]);
        for(int p=2;p<=limit;p<<=1) {
            int len=p>>1,tmp=pow(3,(mod-1)/p);
            for(int k=0;k<limit;k+=p) {
                int buf=1;
                for(int l=k;l<k+len;++l,buf=1ll*buf*tmp%mod) {
                    int t=1ll*f[l+len]*buf%mod;
                    f[l+len]=(f[l]-t+mod)%mod,f[l]=(f[l]+t)%mod;
                }
            }
        }
        if(inv==1) return;
        int sl=pow(limit,mod-2);reverse(f+1,f+limit);
        for(int i=0;i<limit;++i) f[i]=1ll*f[i]*sl%mod;
    }   
    inline void Inv(int*F,int*G,int n) {
        G[0]=pow(F[0],mod-2);
        int len,lim;
        for(len=1;len<(n<<1);len<<=1) {
            lim=len<<1;
            for(int i=0;i<len;++i) A[i]=F[i],B[i]=G[i];
            for(int i=0;i<lim;++i) flip[i]=(flip[i>>1]>>1)|((i&1)?len:0);
            NTT(A,lim,1),NTT(B,lim,1);
            for(int i=0;i<lim;++i) G[i]=1ll*(2ll-1ll*A[i]*B[i]%mod+mod)%mod*B[i]%mod;
            NTT(G,lim,-1);
            for(int i=len;i<lim;++i) G[i]=0;
        }
        for(int i=0;i<len;++i) A[i]=B[i]=0;
        for(int i=n;i<len;++i) G[i]=0;
    }
    inline void Sqrt(int*F,int*G,int n) {
        G[0]=1;
        int *A=C,*B=D,len,lim,inv2=pow(2,mod-2);
        for(len=1;len<(n<<1);len<<=1) {
            lim=len<<1;
            for(int i=0;i<len;++i) A[i]=F[i],B[i]=G[i];
            Inv(G,B,len);
            for(int i=0;i<lim;++i) flip[i]=(flip[i>>1]>>1)|((i&1)?len:0);
            NTT(A,lim,1),NTT(B,lim,1);
            for(int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod;
            NTT(A,lim,-1);
            for(int i=0;i<lim;++i) G[i]=1ll*(G[i]+A[i])%mod*inv2%mod;
            for(int i=len;i<lim;++i) G[i]=0;
        }
        for(int i=0;i<len;++i) A[i]=B[i]=0;
        for(int i=n;i<len;++i) G[i]=0;
    }
}

int C[N],A[N],B[N],n,m,len=1;
int main() {
    freopen("3625.in","r",stdin);
    freopen("3625.out","w",stdout);
    IN(n),IN(m);
    for(int i=1,x;i<=n;++i) IN(x),C[x]=1;
    while(len<=m) len<<=1;
    for(int i=0;i<len;++i) C[i]=(mod-4ll*C[i]%mod+mod)%mod;
    C[0]=1;
    Poly::Sqrt(C,A,len),A[0]=(A[0]+1)%mod,Poly::Inv(A,B,len);
    for(int i=1;i<=m;++i) printf("%d\n",(B[i]+B[i])%mod);
    return 0;
}
最后修改:2019 年 09 月 18 日 02 : 33 PM

发表评论