首页 > 代码库 > FFT模板(BZOJ2179)
FFT模板(BZOJ2179)
实现了两个长度为n的大数相乘。
#include <cstdio> #include <cmath> #include <complex> using namespace std; #define pi acos(-1) typedef complex<double> C; const int N = 131100; char s[N],t[N]; int n,m,l,r[N],c[N]; C a[N],b[N]; void fft(C *a, int f) { for(int i = 0; i < n; i++) if(r[i] > i) swap(a[i], a[r[i]]); for(int i = 1; i < n; i <<= 1) { C wn(cos(pi/i), f*sin(pi/i)); for(int j = 0; j < n; j += i<<1) { C w = 1; for(int k = 0; k < i; k++, w *= wn) { C x = a[j+k], y = w*a[j+k+i]; a[j+k] = x+y, a[j+k+i] = x-y; } } } } int main() { scanf("%d%s%s", &m, s, t); for(int i = 0; i < m; i++) a[i] = s[m-i-1]-‘0‘, b[i] = t[m-i-1]-‘0‘; for(n = 1, m <<= 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 < n; i++) a[i] /= n; 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; } else if(!c[i] && i == m-1) m--; for(int i = m-1; ~i; i--) printf("%d", c[i]); return 0; }
FFT模板(BZOJ2179)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。