bzoj 2179 [快速傅里叶变换]

题目

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

输入

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

输出

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

样例输入

1 3 4

样例输出

12

数据范围

n<=60000

分析

FFT模板题,求卷积

完整代码

#include<bits/stdc++.h> #define maxn 150000 #define pi acos(-1.0) //#define DEBUG using namespace std; int n,out=0; int ans[maxn]; char x[maxn]; complex<double> a[maxn],b[maxn]; inline int read() { char ch; int read=0; bool sign=1; do ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-'); if(ch=='-') sign=-1,ch=getchar(); while(ch>='0'&&ch<='9') { read=read*10+ch-'0'; ch=getchar(); } return read*sign; } inline int Power2(int x) { int x0=1; for(x0=1; x0<x; x0<<=1); return x0; } inline int lg(int n) { int l=0; if(n==0) return 0; for(int x=1; x<=n; x<<=1) l++; return l; } inline int rev(int x,int n) { int out=0; while(n--) out=(out+(x&1))<<1,x>>=1; return out>>1; } void FFT(complex<double> a[],int n,int flag) { complex<double> A[n+1]; for(int i=0,l=lg(n-1); i<n; ++i) A[rev(i,l)]=a[i]; for(int i=2; i<=n; i<<=1) { complex<double> dw(cos(2*pi/i),sin(2*pi*flag/i)); for(int j=0; j<n; j+=i) { complex<double> w(1.0,0); for(int k=0; k<(i>>1); ++k,w=w*dw) { complex<double> u=A[j+k]; complex<double> t=w*A[j+k+(i>>1)]; A[j+k]=u+t; A[j+k+(i>>1)]=u-t; } } if(flag==-1) for(int i=0; i<n; ++i) ans[i]=int(A[i].real()/n+0.5); else for(int i=0; i<n; ++i) a[i]=A[i]; } } int main() { // freopen("in.txt","r",stdin); // freopen("mine.txt","w",stdout); scanf("%d",&n); scanf("%s",x); for(int i=0; i<n; ++i) a[i]=x[n-i-1]-'0'; #ifdef DEBUG for(int i=0;i<n;++i) cerr<<a[i].real()<<" "; #endif scanf("%s",x); for(int i=0; i<n; ++i) b[i]=x[n-i-1]-'0'; int length=Power2(n*2); FFT(a,length,1); FFT(b,length,1); for(int i=0; i<=length; ++i) a[i]*=b[i]; FFT(a,length,-1); int m=2*n; for(int i=0; i<=m; ++i) { ans[i+1]+=ans[i]/10; ans[i]=ans[i]%10; } int wei=2*n+1; while(ans[wei]==0) wei--; for(int i=wei; i>=0; --i) putchar(ans[i]+'0'); #ifdef DEBUG for(int i=0; i<n*2; ++i) cerr<<ans[i]<<" "; #endif // DEBUG return 0; }