codeforces #250E The Child and Binary Tree 快速傅裡葉變換

codeforces #250E The Child and Binary Tree 快速傅裡葉變換

題目大意：給定一個集合S，對於i=1...m求有多少二叉樹滿足每個節點的權值都在集合S中且權值和為i
構造答案多項式F(x)和集合S的生成函數C(x)，那麼
根節點的左子樹是一棵二叉樹，右子樹是一棵二叉樹，本身的權值必須在集合S中，此外還有空樹的情況
故有F(x)=F2(x)C(x)+1
解得F(x)=1±1?4C(x)√2C(x)=21±1?4C(x)√
若等式下方取減號則分母不可逆，捨去
得到F(x)=21+1?4C(x)√
有關多項式求逆和多項式開根的內容參見Picks的博客
CF上每個點7s時限能過 BZ上我實在沒心情卡常數了
[捂臉熊]我整個人都快速傅裡葉變換了

#include 
#include 
#include 
#include 
#define M 525000
#define P 998244353
#define G 3
#define INV2 499122177
using namespace std;

int n,m,l;

int a[M],b[M];

long long Quick_Power(long long x,long long y)
{
    long long re=1;
    while(y)
    {
        if(y&1) (re*=x)%=P;
        (x*=x)%=P; y>>=1;
    }
    return re;
}

void FFT(int a[],int n,int type)
{
    static int temp[M];
    int i;
    if(n==1) return ;
    for(i=0;i>1]=a[i],temp[i+n>>1]=a[i+1];
    memcpy(a,temp,sizeof(a[0])*n);
    int *l=a,*r=a+(n>>1);
    FFT(l,n>>1,type);
    FFT(r,n>>1,type);
    long long w=Quick_Power(G,(long long)(P-1)/n*type%(P-1)),wn=1;
    for(i=0;i>1;i++,(wn*=w)%=P)
        temp[i]=(l[i]+wn*r[i])%P,temp[i+(n>>1)]=(l[i]-wn*r[i]%P+P)%P;
    memcpy(a,temp,sizeof(a[0])*n);
}

void Get_Inv(int a[],int b[],int n)
{
    static int temp[M];
    int i;
    if(n==1)
    {
        b[0]=Quick_Power(a[0],P-2);
        return ;
    }
    Get_Inv(a,b,n>>1);
    memcpy(temp,a,sizeof(a[0])*n);
    memset(temp+n,0,sizeof(a[0])*n);
    FFT(temp,n<<1,1);
    FFT(b,n<<1,1);
    for(i=0;i>1);
    memset(b_inv,0,sizeof(a[0])*n);
    Get_Inv(b,b_inv,n);
    memcpy(temp,a,sizeof(a[0])*n);
    memset(temp+n,0,sizeof(a[0])*n);
    FFT(temp,n<<1,1);
    FFT(b,n<<1,1);
    FFT(b_inv,n<<1,1);
    for(i=0;i>n>>m;
    for(l=1;l<=m;l<<=1);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x<=m) a[x]-=4;
        if(a[x]<0) a[x]+=P;
    }
    a[0]=1;
    Get_Root(a,b,l);
    static int c[M],d[M];
    memcpy(c,b,sizeof(a[0])*l);
    (++c[0])%=P;
    Get_Inv(c,d,l);
    for(i=1;i<=m;i++)
        printf("%d\n",(d[i]<<1)%P);
    return 0;
}