BZOJ 3456 城市規劃 快速傅裡葉變換

BZOJ 3456 城市規劃 快速傅裡葉變換

題目大意：求n個點的無向簡單連通圖個數，n≤1.3?105
遞推式：fi=2C2i?∑i?1j=1fj?Cj?1i?1?2C2i?j
推導戳這裡
然後兩側同除(i?1)!得到：
fi(i?1)!=2C2i(i?1)!?∑i?1j=1fj?2C2i?j(j?1)!?(i?j)!

∑ij=1fj?2C2i?j(j?1)!?(i?j)!=2C2i(i?1)!

∑ij=1fj(j?1)!?2C2i?j(i?j)!=2C2i(i?1)!

這顯然是一個卷積的形式

然後我們令：
A=∑ni=1fi(i?1)!xi
B=∑ni=02C2ii!xi
C=∑ni=12C2i(i?1)!xi
那麼有A?B=C
然後有A≡C?B?1(mod xn+1)
多項式求逆搞一搞就好了
沒想到還真有人的FFT比我還慢2333

#include 
#include 
#include 
#include 
#define M 263000
#define MOD 1004535809
#define G 3
using namespace std;
int n,m;
long long Quick_Power(long long x,long long y)
{
    long long re=1;
    while(y)
    {
        if(y&1) (re*=x)%=MOD;
        (x*=x)%=MOD; 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)(MOD-1)/n*type%(MOD-1)),wn=1;
    for(i=0;i>1;i++,(wn*=w)%=MOD)
        temp[i]=(l[i]+wn*r[i])%MOD,temp[i+(n>>1)]=(l[i]-wn*r[i]%MOD+MOD)%MOD;
    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],MOD-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>n;
    for(m=1;m<=n;m<<=1);
    for(fac[0]=1,i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%MOD;
    for(i=0;i<=n;i++)
        B[i]=Quick_Power(2,((long long)i*(i-1)>>1)%(MOD-1))*Quick_Power(fac[i],MOD-2)%MOD;
    for(i=1;i<=n;i++)
        C[i]=Quick_Power(2,((long long)i*(i-1)>>1)%(MOD-1))*Quick_Power(fac[i-1],MOD-2)%MOD;
    Get_Inv(B,inv_B,m);
    FFT(inv_B,m<<1,1);
    FFT(C,m<<1,1);
    for(i=0;i