BZOJ_2179_FFT快速傅立叶_(FFT)

描述


http://www.lydsy.com/JudgeOnline/problem.php?id=2179

超大整数乘法

分析


FFT模板题.

把数字看成是多项式,x是10.然后用FFT做多项式乘法,最后进位就好了.

注意:

1.进位前要把每一位加0.5(或者更小),然后向下取整,应该是浮点数的计算误差吧...

 #include <bits/stdc++.h>
using namespace std; const int maxn=;
const double pi=acos(-1.0);
int len;
int rev[maxn],ans[maxn];
char str[maxn];
struct cp{//复数(complex)
double r,i;
cp(double r_=0.0,double i_=0.0):r(r_),i(i_){}
cp operator + (const cp &x) const { return cp(r+x.r,i+x.i); }
cp operator - (const cp &x) const { return cp(r-x.r,i-x.i); }
cp operator * (const cp &x) const { return cp(r*x.r-i*x.i,r*x.i+i*x.r); }
}a[maxn],b[maxn],A[maxn];
void brc(int &len){//二进制逆序置换(bit-reverse-copy)
memset(rev,-,sizeof rev);
int k=,l=;
while(k<len) k<<=,l++;
len=k;
rev[]=; rev[len-]=len-;
for(int i=;i<len-;i++){
if(rev[i]!=-) continue;
int x=i,y=,m=l;
while(m--) y<<=, y|=(x&), x>>=;
rev[i]=y; rev[y]=i;
}
}
void dft(cp *a,int n,int flag){//离散傅里叶变换(discrete-Fourier-transform)
for(int i=;i<n;i++) A[rev[i]]=a[i];
for(int i=;i<n;i++) a[i]=A[i];
for(int m=;m<=n;m<<=){
cp wn(cos(2.0*pi/m*flag),sin(2.0*pi/m*flag));
for(int i=;i<n;i+=m){
cp w(1.0,0.0); int k=m>>;
for(int j=;j<k;j++){
cp t=w*a[i+j+k], u=a[i+j];
a[i+j]=u+t;
a[i+j+k]=u-t;
w=w*wn;
}
}
}
if(flag==-)for(int i=;i<n;i++) a[i].r/=n;
}
void readin(cp *a){
scanf("%s",str);
int l=strlen(str);
for(int i=;i<l;i++) a[i].r=str[l--i]-'';
}
int main(){
scanf("%d",&len);
len=len*-;
readin(a); readin(b);
brc(len);
dft(a,len,); dft(b,len,);
for(int i=;i<len;i++) a[i]=a[i]*b[i];
dft(a,len,-);
for(int i=;i<len;i++) ans[i]=a[i].r+0.5;
for(int i=;i<len;i++) ans[i+]+=ans[i]/, ans[i]%=;
len++;
while(!ans[len]&&len) len--;
for(int i=len;i>=;i--) printf("%d",ans[i]);
return ;
}

2179: FFT快速傅立叶

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 2567  Solved: 1308
[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

HINT

Source

上一篇:Windows下安装MySQL详细教程


下一篇:Filemanager 的使用