首页 > 代码库 > BZOJ 2179: FFT快速傅立叶

BZOJ 2179: FFT快速傅立叶

2024-09-05 06:22:38   221人阅读

2179: FFT快速傅立叶

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

分析：

FFT板子...

copy--hzwer...

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<complex> #include<cstdio>//by NeighThorn#define pi acos(-1)using namespace std;typedef complex<double> M;const int maxn=131072;int n,m,L,c[maxn],R[maxn];char ch[maxn];M a[maxn],b[maxn];inline void FFT(M *a,int f){	for(int i=0;i<n;i++)		if(i<R[i]) swap(a[i],a[R[i]]);	for(int i=1;i<n;i<<=1){		M wn(cos(pi/i),f*sin(pi/i));		for(int j=0;j<n;j+=(i<<1)){			M w(1,0);			for(int k=0;k<i;k++,w*=wn){				M x=a[j+k],y=w*a[j+k+i];				a[j+k]=x+y,a[j+k+i]=x-y;			}		}	}	if(f==-1) 		for(int i=0;i<n;i++)			a[i]/=n;}signed main(void){	scanf("%d",&n);n--;	scanf("%s",ch);	for(int i=0;i<=n;i++) a[i]=ch[n-i]-‘0‘;	scanf("%s",ch);	for(int i=0;i<=n;i++) b[i]=ch[n-i]-‘0‘;	m=n<<1;for(n=1;n<=m;n<<=1) L++;	for(int i=0;i<n;i++) 		R[i]=(R[i>>1]>>1|((i&1)<<(L-1)));	FFT(a,1);FFT(b,1);	for(int i=0;i<=n;i++) a[i]*=b[i];	FFT(a,-1);	for(int i=0;i<=m;i++) c[i]=(int)(a[i].real()+0.1);	for(int i=0;i<=m;i++)		if(c[i]>=10){			c[i+1]+=c[i]/10,c[i]%=10;			if(i==m) m++;		}	for(int i=m;i>=0;i--) printf("%d",c[i]);puts("");	return 0;}

　　

By NeighThorn

BZOJ 2179: FFT快速傅立叶


联系
我们