FFT模板(BZOJ2179)
2024-10-10 14:02:32
实现了两个长度为n的大数相乘。
#include <cstdio>
#include <cmath>
#include <complex>
using namespace std;
#define pi acos(-1) typedef complex<double> C;
const int N = ;
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 = ; i < n; i++) if(r[i] > i) swap(a[i], a[r[i]]);
for(int i = ; i < n; i <<= ) {
C wn(cos(pi/i), f*sin(pi/i));
for(int j = ; j < n; j += i<<) {
C w = ;
for(int k = ; 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 = ; i < m; i++) a[i] = s[m-i-]-'', b[i] = t[m-i-]-'';
for(n = , m <<= ; n < m; n <<= ) l++;
for(int i = ; i < n; i++) r[i] = (r[i>>]>>)|((i&)<<(l-));
fft(a, ), fft(b, );
for(int i = ; i < n; i++) a[i] *= b[i];
fft(a, -);
for(int i = ; i < n; i++) a[i] /= n;
for(int i = ; i < m; i++) c[i] = (int)(a[i].real()+0.1);
for(int i = ; i < m; i++) if(c[i] >= ) {
c[i+] += c[i]/, c[i] %= ;
} else if(!c[i] && i == m-) m--;
for(int i = m-; ~i; i--) printf("%d", c[i]);
return ;
}
最新文章
- dateRangePicker时间范围控件
- Linux下高cpu解决方案(转载)
- html5 Application Cache——加快简历二次访问速度
- [js开源组件开发]query组件,获取url参数和form表单json格式
- struts2中valueStack,stackContext以及actionContext的关系
- SHAREPOINT 工作流审批权限问题
- [转]C# List<;T>;的详细用法
- C#通过WinAPI获取内存信息,32位64位可用
- POJ 3258
- c#中 HttpContext作用(一)【转】
- 解密电子书之二:EPD控制芯片
- Struts2--Action属性接收参数
- LDA
- Linux 驱动——Button驱动7(Timer)消抖
- VBA果然很强大
- [转].NET 性能测试工具 -- 事件跟踪器(ETW)
- Flex的一些小实例
- springboot mybatis 分页整合
- MIT molecular Biology 笔记10 翻译
- [原创]WebScarab工具介绍