HDU 1402 A * B Problem Plus(FFT)
2024-10-18 21:22:30
Problem Description
Calculate A * B.
Input
Each line will contain two integers A and B. Process to end of file.
Note: the length of each integer will not exceed 50000.
Output
For each case, output A * B in one line.
题目大意:求A * B。
思路:快速傅里叶变换的模板题,偷的模板……也不知道使用姿势对不对QAQ。
代码(250MS):(Update:2014年11月16日)
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <complex>
using namespace std;
typedef complex<double> Complex;
const double PI = acos(-); void fft_prepare(int maxn, Complex *&e) {
e = new Complex[ * maxn - ];
e += maxn - ;
e[] = ;
for (int i = ; i < maxn; i <<= )
e[i] = Complex(cos( * PI * i / maxn), sin( * PI * i / maxn));
for (int i = ; i < maxn; i++)
if ((i & -i) != i) e[i] = e[i - (i & -i)] * e[i & -i];
for (int i = ; i < maxn; i++) e[-i] = e[maxn - i];
}
/* f = 1: dft; f = -1: idft */
void dft(Complex *a, int N, int f, Complex *e, int maxn) {
int d = maxn / N * f;
Complex x;
for (int n = N, m; m = n / , m >= ; n = m, d *= )
for (int i = ; i < m; i++)
for (int j = i; j < N; j += n)
x = a[j] - a[j + m], a[j] += a[j + m], a[j + m] = x * e[d * i];
for (int i = , j = ; j < N - ; j++) {
for (int k = N / ; k > (i ^= k); k /= );
if (j < i) swap(a[i], a[j]);
}
} const int MAXN = ;
Complex x1[MAXN], x2[MAXN];
char s1[MAXN / ], s2[MAXN / ];
int sum[MAXN]; int main() {
Complex* e = ;
fft_prepare(MAXN, e);
while(scanf("%s%s",s1,s2) != EOF) {
int n1 = strlen(s1);
int n2 = strlen(s2);
int n = ;
while(n < n1 * || n < n2 * ) n <<= ;
for(int i = ; i < n; ++i) {
x1[i] = i < n1 ? s1[n1 - - i] - '' : ;
x2[i] = i < n2 ? s2[n2 - - i] - '' : ;
} dft(x1, n, , e, MAXN);
dft(x2, n, , e, MAXN);
for(int i = ; i < n; ++i) x1[i] = x1[i] * x2[i];
dft(x1, n, -, e, MAXN);
for(int i = ; i < n; ++i) x1[i] /= n; for(int i = ; i < n; ++i) sum[i] = round(x1[i].real());
for(int i = ; i < n; ++i) {
sum[i + ] += sum[i] / ;
sum[i] %= ;
} n = n1 + n2 - ;
while(sum[n] <= && n > ) --n;
for(int i = n; i >= ;i--) printf("%d", sum[i]);
puts("");
}
}
最新文章
- LeetCode 094 Binary Tree Inorder Traversal
- CMD打包文件,解压文件
- 链表的C++实现——创建-插入-删除-输出-清空
- jQuery 判断页面元素是否存在
- sequenza细胞纯度计算
- 【转】eclipse 安装插件
- (转)PK系列之六:该不该读中文翻译的专业书
- JavaScript ECAMScript5 新特性——get/set访问器
- vlc_input buffer管理 &; 时钟同步(转)
- .net后台 Silverlight 页面 动态设置 ASPX 页面 控件的Margin值(位置设置)
- Office——检索 COM 类工厂中 CLSID 为 {000209FF-0000-0000-C000-000000000046} 的组件时失败
- 微信小程序实现简易留言板
- 支持ipV6和ipV4的客户端编程
- pythn print格式化输出---------";%s 和 % d"; 都是什么意思?
- 激活miniconda2环境,出现activate命令不存在的解决方案(activate: No such file or directory)
- [Bayes] prod: M-H: Independence Sampler for Posterior Sampling
- 安装node.msi 格式的文件失败
- 事务的ACID性质
- kettle学习笔记(三)——kettle资源库、运行方式与日志
- 解决WIN32窗口不响应WM_LBUTTONDBLCLK消息