洛谷P1919 【模板】A*B Problem升级版 题解(FFT的第一次实战)
洛谷P1919 【模板】A*B Problem升级版(FFT快速傅里叶)
刚学了FFT,我们来刷一道模板题。
题目描述
给定两个长度为 n 的两个十进制数,求它们的乘积。
n<=100000
如果用 n^2 暴力,肯定会 TLE。
我们把这两个数看成一个多项式。
f(x)=a0+a1*101+a2*102+a3*103+ …… +an*10n
然后就可以愉快的FFT求解了!!
1 #include<iostream>
2 #include<cmath>
3 #include<complex>
4 #include<cstdio>
5 using namespace std;
6
7 const double PI=acos(-1);
8 typedef complex<double> cmplx;
9 int rev[1000005];
10 cmplx a[1000005],b[1000005];
11 int n,bit=2,output[1000005];
12 char s1[60005],s2[60005];
13
14 void get_rev(){
15 for(int i=0;i<bit;i++)
16 rev[i]=(rev[i>>1]>>1)|(bit>>1)*(i&1);
17 }
18
19 void FFT(cmplx *a,int dft){
20 for(int i=0;i<bit;i++)
21 if(i<rev[i])swap(a[i],a[rev[i]]);
22 for(int i=1;i<bit;i<<=1){
23 cmplx W=exp(cmplx(0,dft*PI/i));
24 for(int j=0;j<bit;j+=i<<1){
25 cmplx w(1,0);
26 for(int k=j;k<j+i;k++,w*=W){
27 cmplx x=a[k];
28 cmplx y=w*a[k+i];
29 a[k]=x+y;
30 a[k+i]=x-y;
31 }
32 }
33 }
34 if(!~dft)for(int i=0;i<bit;i++)a[i]/=bit;
35 }
36
37 int main(){
38 scanf("%d%s%s",&n,s1,s2);
39 for(int i=1;(1<<i)<=2*n;i++)bit<<=1;
40 for(int i=0;i<n;i++){
41 a[i]=s1[n-i-1]-'0';
42 b[i]=s2[n-i-1]-'0';
43 }
44 get_rev();
45 FFT(a,1),FFT(b,1);
46 for(int i=0;i<bit;i++)a[i]=a[i]*b[i];
47 FFT(a,-1);
48 for(int i=0;i<bit;i++){ //确保输出为十进制
49 output[i]+=a[i].real()+0.5;
50 output[i+1]+=output[i]/10;
51 output[i]%=10;
52 }
53 bool check=false;
54 for(int i=n<<1;i>=0;i--){ //去前导零输出
55 if(check||output[i]){
56 printf("%d",output[i]);
57 check=true;
58 }
59 }
60 if(!check)printf("0");
61 }