The Child and Binary Tree(小朋友和二叉树)[CodeForces 438E][多项式]

题目

Luogu

左右儿子有区别

思路

可以有 $dp$ 转移：$f_i$ 表示权值和为 $i$ 的方案数
$$f_{i+j+c_u}=\sum f_j?f_k$$
然后尝试写成生成函数
$F(x)={\sum }_{i=0}^n{f}_i{x}^i$
发现有个 $+c_u$
可以再定义一个生成函数 $G(x)={\sum }_{i=0}^n[i\in C]x^i$
那么就好起来：
$F(x)=G(x)?F^2(x)$
但是我们需要初值，也就是 $f_0=1$
$F(x)=G(x)?F^2(x)+1$
看成一元二次方程的解
$$F(x)=\frac{1\pm \sqrt{1?4G(x)}}{2G(x)}$$
因为有正负号，我们需要检验
$f_0=1，令x=0$
取+号趋于 $+\infty$
取-号趋于 $1$ 成立
虽然已经可以做了，但是可以好看一点
$$F(x)=\frac{2}{1+\sqrt{1?4G(x)}}$$
然后套用开根和 $Exp+Ln$ 都行

代码

#pragma GCC optimize(2)
#include<set> 
#include<map> 
#include<stack> 
#include<ctime> 
#include<cstdio> 
#include<queue> 
#include<cmath> 
#include<vector> 
#include<cstring> 
#include<climits> 
#include<iostream> 
#include<algorithm>
using namespace std;
#define LL long long
inline int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9'){
    x=x*10+c-'0';c=getchar();}return f*x;
}
#define MAXN 1000000
#define INF 0x3f3f3f3f
const int Mod=998244353,g=3,rg=332748118;
inline int Mul(register LL x,register int y){
    x*=y;return x>=Mod?x%Mod:x;
}
inline int Add(register int x,register int y){
    x+=y;return x>=Mod?x-Mod:x;
}
inline int Pow(register int x,register LL y){
    register int ret=1;while(y){
    if(y&1) ret=Mul(ret,x);x=Mul(x,x),y>>=1;}return ret;
}
int rev[MAXN+5];
int pg[MAXN+5],prg[MAXN+5];
int fac[MAXN+5],ifac[MAXN+5],inv[MAXN+5];inline int Len(register int n){
    register int len,lg2;for(len=1,lg2=0;len<n;len<<=1)lg2++;for(register int i=1;i<=len;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg2-1));return len;}inline void NTT(int *A,int len,register int sign){
    for(register int i=0;i<len;i++)if(i<rev[i]) swap(A[i],A[rev[i]]);for(register int k=1;k<len;k<<=1){
    register int w0=(sign==1?pg[k]:prg[k]);for(register int j=0,siz=k<<1;j<len;j+=siz)for(register int i=0,w=1;i<k;i++,w=Mul(w,w0)){
    register int x=A[i+j],y=Mul(w,A[i+j+k]);A[i+j]=Add(x,y),A[i+j+k]=Add(x,Mod-y);}}if(sign==-1){
    register int Inv=Pow(len,Mod-2);for(register int i=0;i<len;i++)A[i]=Mul(A[i],Inv);}return ;}int tmp1[MAXN+5],tmp2[MAXN+5];inline void Poly_Mul(register int *A,register int*B,register int*C,register int n,register int m){
    //A,B,C均可不清空copy(A,A+n,tmp1),copy(B,B+m,tmp2);register int len=Len(n+m-1);fill(tmp1+n,tmp1+len,0),fill(tmp2+m,tmp2+len,0);NTT(tmp1,len,1),NTT(tmp2,len,1);for(int i=0;i<len;i++)C[i]=Mul(tmp1[i],tmp2[i]);NTT(C,len,-1);return ;}int tmp3[MAXN+5];inline void Poly_Inv(int *A,int *B,register int n){
    //B要清空if(n==1){
    B[0]=Pow(A[0],Mod-2);return ;}Poly_Inv(A,B,(n+1)/2);register int len=Len(2*n);copy(A,A+n,tmp3);fill(tmp3+n,tmp3+len,0),fill(B+n,B+len,0);NTT(tmp3,len,1),NTT(B,len,1);for(int i=0;i<len;i++)B[i]=1ll*(2+Mod-1ll*B[i]*tmp3[i]%Mod)%Mod*B[i]%Mod;NTT(B,len,-1),fill(B+n,B+len,0);return ;}inline void Poly_Deriv(int *A,int *B,register int n){
    for(register int i=1;i<n;i++)B[i-1]=Mul(A[i],i);B[n-1]=0;return ;}inline void Poly_Inter(int *A,int *B,register int n){
    //有取模for(register int i=n-1;i>=1;i--)B[i]=Mul(A[i-1],inv[i]);B[0]=0;return ;}int inva[MAXN+5],da[MAXN+5];inline void Poly_Ln(int *A,int *B,register int n){
    Poly_Inv(A,inva,n);Poly_Deriv(A,da,n);Poly_Mul(inva,da,B,n,n);Poly_Inter(B,B,n);return ;}int cF[MAXN+5];inline void Poly_Exp(int *A,int *B,int n){
    if(n==1){
    B[0]=1;return ;}Poly_Exp(A,B,(n+1)/2),Poly_Ln(B,cF,n);cF[0]=(1+A[0]-cF[0]+Mod)%Mod;for(int i=1;i<n;i++)cF[i]=(A[i]-cF[i]+Mod)%Mod;int len=Len(2*n);fill(cF+n,cF+len,0),fill(B+n,B+len,0);NTT(cF,len,1),NTT(B,len,1);for(int i=0;i<len;i++)B[i]=1ll*B[i]*cF[i]%Mod;NTT(B,len,-1),fill(B+n,B+len,0);return ;}int lna[MAXN+5];inline void Poly_Pow(int *A,int *P,int k,int n){
    Poly_Ln(A,lna,n);for(int i=0;i<n;i++)lna[i]=1ll*lna[i]*k%Mod;Poly_Exp(lna,P,n);return ;}
void Print(int *A,int n){
    for(int i=0;i<n;i++)printf("%lld ",1ll*A[i]*fac[i]%Mod);puts("");return ;
}
#define N 200003
int C[N+5],D[N+5],E[N+5],F[N+5];
int main(){
    fac[0]=1;for(register int k=1;k<MAXN;k<<=1)	pg[k]=Pow(g,(Mod-1)/(k<<1)),prg[k]=Pow(rg,(Mod-1)/(k<<1));for(register int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%Mod;ifac[N]=Pow(fac[N],Mod-2);for(register int i=N-1;i>=0;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%Mod;inv[1]=1;for(register int i=2;i<=N;i++)inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;int n=read(),m=read();for(int i=1;i<=n;i++)C[read()]=1;for(int i=0;i<=m;i++)C[i]=Mod-4ll*C[i]%Mod;C[0]=Add(C[0],1);Poly_Ln(C,D,m+1);for(int i=0;i<=m;i++)D[i]=1ll*D[i]*inv[2]%Mod;Poly_Exp(D,E,m+1);E[0]=Add(E[0],1);Poly_Inv(E,F,m+1);for(int i=1;i<=m;i++)printf("%d\n",F[i]*2%Mod);return 0;
}