首页 > 代码库 > 【BZOJ2179】FFT快速傅立叶
【BZOJ2179】FFT快速傅立叶
【BZOJ2179】FFT快速傅立叶
Description
给出两个n位10进制整数x和y,你需要计算x*y。
Input
第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。
Output
输出一行,即x*y的结果。
Sample Input
1
3
4
3
4
Sample Output
12
数据范围:
数据范围:
n<=60000
题解:板子题,敲板子~
#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#define pi acos(-1.0)using namespace std;struct cp{ double x,y; cp(double x0,double y0) { x=x0,y=y0; } cp(){} cp operator +(const cp a)const { return cp(x+a.x,y+a.y); } cp operator -(const cp a)const { return cp(x-a.x,y-a.y); } cp operator *(const cp a)const { return cp(x*a.x-y*a.y,x*a.y+y*a.x); }}n1[1<<20],n2[1<<20];int n;char str[1<<20];int ans[1<<20];int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘)f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret*f;}void init(cp *a,int len){ int i,j,t=0; for(i=0;i<len;i++) { if(i>t) swap(a[i],a[t]); for(j=(len>>1);(t^=j)<j;j>>=1); }}void FFT(cp *a,int len,int f){ init(a,len); int h,i,j,k; cp t; for(h=2;h<=len;h<<=1) { cp wn(cos(f*2*pi/h),sin(f*2*pi/h)); for(j=0;j<len;j+=h) { cp w(1,0); for(k=j;k<j+h/2;k++) t=w*a[k+h/2],a[k+h/2]=a[k]-t,a[k]=a[k]+t,w=w*wn; } } if(f==-1) for(i=0;i<len;i++) a[i].x=a[i].x/len;}void work(cp *a,cp *b,int len){ FFT(a,len,1),FFT(b,len,1); for(int i=0;i<len;i++) a[i]=a[i]*b[i]; FFT(a,len,-1); for(int i=0;i<len;i++) ans[i]=int(a[i].x+0.1);}int main(){ n=rd(); int i,j,t=0,len=1; while(len<n*2) len<<=1; scanf("%s",str); for(i=0;i<n;i++) n1[n-i-1]=cp(str[i]-‘0‘,0); scanf("%s",str); for(i=0;i<n;i++) n2[n-i-1]=cp(str[i]-‘0‘,0); for(i=n;i<len;i++) n1[i]=n2[i]=cp(0,0); work(n1,n2,len); len=2*n-1; for(i=0;i<=len;i++) ans[i+1]+=ans[i]/10,ans[i]%=10; while(ans[len]<=0&&len) len--; for(i=len;i>=0;i--) printf("%d",ans[i]); return 0;}
【BZOJ2179】FFT快速傅立叶
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。