P1919 【模板】A*B Problem升级版（FFT快速傅里叶）
题目描述
给出两个n位10进制整数x和y，你需要计算x*y。
输入输出格式
输入格式：
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。
输出格式：
输出一行，即x*y的结果。（注意判断前导0）
输入输出样例
说明
数据范围：
n<=60000
来源：bzoj2179
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define maxn 240010 #define PI (acos(-1.0)) using namespace std; int rd[maxn],d[maxn<<1]; char s[maxn]; struct node{ double x,y; node(double a=0,double b=0):x(a),y(b){} node operator + (const node &c) {return node(x+c.x,y+c.y);} node operator - (const node &c) {return node(x-c.x,y-c.y);} node operator * (const node &c) {return node(x*c.x-y*c.y,x*c.y+y*c.x);} node operator / (const int &c) {return node(x/c,y/c);} }a[maxn],b[maxn]; void fft(node *a,int n,int f){ node wn,w,x,y;int i; for(int i=0;i<=n;i++)if(rd[i]>i)swap(a[i],a[rd[i]]); for(int k=1;k<n;k<<=1){ wn=node(cos(PI/k),f*sin(PI/k)); for(int j=0;j<n;j+=k<<1){ for(w=node(1,0),i=0;i<k;i++,w=w*wn){ node x=a[i+j]; node y=a[i+j+k]*w; a[i+j]=x+y; a[i+j+k]=x-y; } } } if(f==-1) for(int i=0;i<n;i++)a[i]=a[i]/n; } int main(){ freopen("testdata.in","r",stdin); int n; scanf("%d",&n);n--; scanf("%s",s); for(int i=0;i<=n;i++)a[i].x=s[i]-'0'; scanf("%s",s); for(int i=0;i<=n;i++)b[i].x=s[i]-'0'; int m=n+n,l=0;n=1; while(n<=m)n<<=1,l++; for(int i=0;i<=n;i++)rd[i]=(rd[i>>1]>>1)|((i&1)<<(l-1)); fft(a,n,1);fft(b,n,1); for(int i=0;i<=n;i++)a[i]=a[i]*b[i]; fft(a,n,-1); for(int i=1,j=m+1;i<=m+1;i++,j--) d[j]=(int)(a[i-1].x+0.5); for(int i=1;i<=n;i++)d[i+1]+=d[i]/10,d[i]%=10; while(!d[n]&&n)n--; if(n!=0)for(int i=n;i>=1;i--)printf("%d",d[i]); else puts("0"); return 0; }