【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

上一篇:perforce变量配置与使用


下一篇:算法——三角形图形