首页 > 代码库 > 【BZOJ】2179: FFT快速傅立叶(fft)

【BZOJ】2179: FFT快速傅立叶(fft)

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

fft裸题。。。。

为嘛我的那么慢。。。。1000多ms。。

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)struct cp {	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); }};const int N=200005;const double PI=acos(-1.0);cp A[N];int rev[N];void dft(cp *a, int n, int flag) {	rep(i, n) A[rev[i]]=a[i];	rep(i, n) a[i]=A[i];	for(int m=2; m<=n; m<<=1) {		cp wn(cos(2.0*PI/m*flag), sin(2.0*PI/m*flag));		for(int i=0; i<n; i+=m) {			cp w(1.0); int mid=m>>1;			for(int j=0; j<mid; ++j) {				cp u=a[i+j+mid]*w, t=a[i+j];				a[i+j]=t+u;				a[i+j+mid]=t-u;				w=w*wn;			}		}	}	if(flag==-1) rep(i, n) a[i].r/=n;}void init(int &len) {	int k=1, L=0;	while(k<len) k<<=1, ++L;	len=k;	rep(i, len) {		int t=i, r=0; k=L;		while(k--) r<<=1, r|=(t&1), t>>=1;		rev[i]=r;	}}int len, ans[N];char s[N];cp a[N], b[N];void readin(cp *a) {	scanf("%s", s);	int n=strlen(s);	rep(i, n) a[i].r=s[n-i-1]-‘0‘;}int main() {	read(len); len=len*2-1;	readin(a); readin(b);	init(len);	dft(a, len, 1); dft(b, len, 1);	rep(i, len) a[i]=a[i]*b[i];	dft(a, len, -1);	rep(i, len) ans[i]=a[i].r+0.5;	rep(i, len) ans[i+1]+=ans[i]/10, ans[i]%=10;	++len;	while(!ans[len] && len) --len;	for3(i, len, 0) printf("%d", ans[i]);	return 0;}

  

 


 

 

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

【BZOJ】2179: FFT快速傅立叶(fft)