【bzoj2179】FFT快速傅立叶 FFT模板

2016-06-01  09:34:54

很久很久很久以前写的了。。。

今天又比较了一下效率,貌似手写复数要快很多。

贴一下模板:

 #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<complex>
#define ll long long
#define N 500020
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct CD{
double a,b;
CD(double x=,double y=){a=x;b=y;}
friend CD operator +(CD n1,CD n2){return CD(n1.a+n2.a,n1.b+n2.b);}
friend CD operator -(CD n1,CD n2){return CD(n1.a-n2.a,n1.b-n2.b);}
friend CD operator *(CD n1,CD n2){return CD(n1.a*n2.a-n1.b*n2.b,n1.a*n2.b+n1.b*n2.a);}
};
int n,m,bit=;
const long double Pi=acos(-1.0); void FFT(CD *a,int n,int type){
for(int i=,j=;i<n;i++) {
if(j>i)swap(a[i],a[j]);
int k=n;
while(j&(k >>= ))j&=~k;
j|=k;
}
for(int i=;i<=bit;i++){
CD w_n(cos(*type*Pi/(<<i)),sin(*type*Pi/(<<i)));
for(int j=;j<(<<bit);j+=(<<i)){
CD w(,);
for(int k=j;k<j+(<<(i-));k++){
CD tmp=a[k],tt=w*a[k+(<<(i-))];
a[k]=a[k]+tt;
a[k+(<<(i-))]=tmp-tt;
w=w*w_n;
}
}
}
if(type<) for(int i=;i<(<<bit);i++) a[i].a=(a[i].a+0.5)/(<<bit);
} CD poly1[N],poly2[N];
int c[N*]; char ch[N];
int main (){
n=read();
scanf("%s",ch+);
for(int i=;i<n;i++)poly1[i]=(double)(ch[n-i]-'');
scanf("%s",ch+);
for(int i=;i<n;i++)poly2[i]=(double)(ch[n-i]-'');
bit=;
while(<<bit<(n<<))bit++;
n=<<bit;
FFT(poly1,n,);FFT(poly2,n,);
for(int i=;i<n;i++)poly1[i]=poly1[i]*poly2[i];
FFT(poly1,n,-);
int jin=,top=;
for(int i=;i<n;i++){
jin+=(int)(poly1[i].a+0.5);
c[++top]=jin%;
jin/=;
}
while(top&&c[top]==) top--;
while(top)putchar(c[top--]+'');
return ;
}

2179: FFT快速傅立叶

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 2552  Solved: 1299
[Submit][Status][Discuss]

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

上一篇:odoo action方法


下一篇:c++实现状态模式