首页 > 代码库 > 【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
3
4
Sample Output
12
数据范围:
n<=60000
数据范围:
n<=60000
HINT
Source
【BZOJ】2179: FFT快速傅立叶(fft)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。