2179: FFT快速傅立叶
Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 3308 Solved: 1720Description
给出两个n位10进制整数x和y,你需要计算x*y。Input
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。Output
输出一行,即x*y的结果。Sample Input
1
3
4Sample Output
12数据范围:
n<=60000HINT
Source
【分析】
FFT裸题。
结果的第i位 f*g(i)=f(k)*g(i-k) 【后面就会知道,这是标准的卷积形式,可以用FFT加速
FFTnlogn的,后面总结。
现在还是只会递归版本。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define Maxn 60010*4
const double pi=3.14159265358; struct P
{
double x,y;
P() {x=y=;}
P(double x,double y):x(x),y(y){}
friend P operator + (P x,P y) {return P(x.x+y.x,x.y+y.y);}
friend P operator - (P x,P y) {return P(x.x-y.x,x.y-y.y);}
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);}
}a[Maxn],b[Maxn]; char ss[Maxn];
int ans[Maxn]; void fft(P *s,int n,int f)
{
if(n==) return;
P a0[n>>],a1[n>>];
for(int i=;i<=n;i+=) a0[i>>]=s[i],a1[i>>]=s[i+];
fft(a0,n>>,f);fft(a1,n>>,f);
P wn(cos(*pi/n),f*sin(*pi/n)),w(,);
for(int i=;i<(n>>);i++,w=w*wn) s[i]=a0[i]+w*a1[i],s[i+(n>>)]=a0[i]-w*a1[i];
} int main()
{
int n;
scanf("%d",&n);n--;
scanf("%s",ss);
for(int i=;i<=n;i++) a[n-i].x=(ss[i]-'');
scanf("%s",ss);
for(int i=;i<=n;i++) b[n-i].x=(ss[i]-'');
int nn=;
while(nn<=*n) nn<<=;
fft(a,nn,);fft(b,nn,);
for(int i=;i<=nn;i++) a[i]=a[i]*b[i];
fft(a,nn,-);
memset(ans,,sizeof(ans));
for(int i=;i<=*n;i++) ans[i]=(int)(a[i].x/nn+0.5);
for(int i=;i<=*n;i++) ans[i+]+=ans[i]/,ans[i]%=;
int ll=*n;
while(ans[ll+]!=) ans[ll+]+=ans[ll+]/,ans[++ll]%=;
while(ll>&&ans[ll]==) ll--;
for(int i=ll;i>=;i--) printf("%d",ans[i]);//printf("\n");
return ;
}
2017-04-14 11:52:12