[BZOJ2179]FFT快速傅立叶

 1 #include<cstdio>
 2 #include<cmath>
 3 const int P=(1<<21)*479+1;
 4 typedef long long ll;
 5 ll power(ll t,int k,int mod){ll f=1;for(;k;k>>=1,t=t*t%mod)if(k&1)f=f*t%mod;return f;}
 6 int a[132000],b[132000],n,m,k,w[2][132000],f;
 7 void FFT(int x[],int k,int v)
 8 {
 9     int i,j,l,tmp;
10     for(i=j=0;i<k;i++)
11     {
12         if(i>j)tmp=x[i],x[i]=x[j],x[j]=tmp;
13         for(l=k>>1;(j^=l)<l;l>>=1);
14     }
15     for(i=2;i<=k;i<<=1)
16     for(j=0;j<k;j+=i)
17     for(l=0;l<i>>1;l++)
18     {
19         tmp=1LL*x[j+l+(i>>1)]*w[v][k/i*l]%P;
20         x[j+l+(i>>1)]=(1LL*x[j+l]-tmp+P)%P;
21         x[j+l]=(1LL*x[j+l]+tmp)%P;
22     }
23 }
24 int main(){
25     scanf("%d\n",&n);int i,j;
26     for(i=0;i<n;i++)a[n-i-1]=getchar()-‘0‘;getchar();
27     for(i=0;i<n;i++)b[n-i-1]=getchar()-‘0‘;
28     for(k=1;k<n<<1;k<<=1);
29     w[0][0]=w[0][k]=1;j=power(3,(P-1)/k,P);
30     for(i=1;i<k;i++)w[0][i]=1LL*w[0][i-1]*j%P;
31     for(i=0;i<=k;i++)w[1][i]=w[0][k-i];
32     FFT(a,k,0);FFT(b,k,0);
33     for(i=0;i<k;i++)a[i]=1LL*a[i]*b[i]%P;
34     FFT(a,k,1);j=power(k,P-2,P);
35     for(i=0;i<2*n-1;i++)a[i]=1LL*a[i]*j%P;
36     for(i=0;i<2*n-1;i++)
37     if(a[i]>9)a[i+1]+=a[i]/10,a[i]%=10;
38     if(a[2*n-1])printf("%d",a[2*n-1]);
39     for(i=2*n-2;~i;i--)printf("%d",a[i]);
40 }