【BZOJ 2179】 2179: FFT快速傅立叶 (FFT)

2179: FFT快速傅立叶
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 3308 Solved: 1720
Description

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

Input

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

Output

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

Sample Input

1
3
4

Sample Output

12

数据范围：
n<=60000

HINT

Source

【分析】

　　FFT裸题。

　　结果的第i位 f*g(i)=f(k)*g(i-k) 【后面就会知道，这是标准的卷积形式，可以用FFT加速

　　FFTnlogn的，后面总结。

现在还是只会递归版本。。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 #define Maxn 60010*4
 9 const double pi=3.14159265358;
10 
11 struct P
12 {
13     double x,y;
14     P() {x=y=0;}
15     P(double x,double y):x(x),y(y){}
16     friend P operator + (P x,P y) {return P(x.x+y.x,x.y+y.y);}
17     friend P operator - (P x,P y) {return P(x.x-y.x,x.y-y.y);}
18     friend P operator * (P x,P y) {return P(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}
19 }a[Maxn],b[Maxn];
20 
21 char ss[Maxn];
22 int ans[Maxn];
23 
24 void fft(P *s,int n,int f)
25 {
26     if(n==1) return;
27     P a0[n>>1],a1[n>>1];
28     for(int i=0;i<=n;i+=2) a0[i>>1]=s[i],a1[i>>1]=s[i+1];
29     fft(a0,n>>1,f);fft(a1,n>>1,f);
30     P wn(cos(2*pi/n),f*sin(2*pi/n)),w(1,0);
31     for(int i=0;i<(n>>1);i++,w=w*wn) s[i]=a0[i]+w*a1[i],s[i+(n>>1)]=a0[i]-w*a1[i];
32 }
33 
34 int main()
35 {
36     int n;
37     scanf("%d",&n);n--;
38     scanf("%s",ss);
39     for(int i=0;i<=n;i++) a[n-i].x=(ss[i]-'0');
40     scanf("%s",ss);
41     for(int i=0;i<=n;i++) b[n-i].x=(ss[i]-'0');
42     int nn=1;
43     while(nn<=2*n) nn<<=1;
44     fft(a,nn,1);fft(b,nn,1);
45     for(int i=0;i<=nn;i++) a[i]=a[i]*b[i];
46     fft(a,nn,-1);
47     memset(ans,0,sizeof(ans));
48     for(int i=0;i<=2*n;i++) ans[i]=(int)(a[i].x/nn+0.5);
49     for(int i=0;i<=2*n;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;
50     int ll=2*n;
51     while(ans[ll+1]!=0) ans[ll+2]+=ans[ll+1]/10,ans[++ll]%=10;
52     while(ll>1&&ans[ll]==0) ll--;
53     for(int i=ll;i>=0;i--) printf("%d",ans[i]);//printf("
");
54     return 0;
55 }

View Code

2017-04-14 11:52:12