首页 > 代码库 > [BZOJ2179]FFT快速傅立叶

[BZOJ2179]FFT快速傅立叶

2024-07-12 23:07:33   217人阅读

Description

给出两个n位10进制整数x和y，你需要计算x*y。

Input

第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。

Output

输出一行，即x*y的结果。

Sample Input

1
3
4

Sample Output

12

HINT

n<=60000

 

Solution

　　今天终于把数论版的弄好了。之前好像是因为1LL没加调不出来。

　　觉得压位会快很多，但是Wa了半天，不管了。。。

 

 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 }
View Code


联系
我们