博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
递归FFT
阅读量:5958 次
发布时间:2019-06-19

本文共 1177 字,大约阅读时间需要 3 分钟。

#include 
#include
#include
#include
const int mx_n = 4e5 + 10;const double pi = acos(-1.0);#define rep(i, s, t) for(register int i = s; i <= t; ++i)using namespace std;typedef complex
LF;void DFT(LF *p, int n, int f) { if(n == 1) return ; n >>= 1; LF p0[n], p1[n]; rep(i, 0, n-1) p0[i] = p[i<<1], p1[i] = p[i<<1|1]; DFT(p0, n, f), DFT(p1, n, f); LF e(1, 0), w(cos(2*pi/(n<<1)), f*sin(2*pi/(n<<1))); rep(i, 0, n-1) { p[i] = p0[i] + e * p1[i]; p[i+n] = p0[i] - e * p1[i]; e = e * w; }}int n, m;LF a[mx_n], b[mx_n], c[mx_n];int main() {#ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("res.out", "w", stdout);#endif scanf("%d%d", &n, &m); rep(i, 0, n) scanf("%lf", &a[i]); rep(i, 0, m) scanf("%lf", &b[i]); int N = 1; for(; N <= n + m; N <<= 1); DFT(a, N, 1), DFT(b, N, 1); rep(i, 0, N-1) c[i] = a[i] * b[i]; DFT(c, N, -1); rep(i, 0, n + m) printf("%d%c", (int)(c[i].real()/N + 0.5), i ^ (n+m)? ' ':'\n'); return 0;}

转载于:https://www.cnblogs.com/pbvrvnq/p/8530143.html

你可能感兴趣的文章
利用单壁路由实现vlan间路由
查看>>
hello world
查看>>
CentOS 7 配置yum本地base源和阿里云epel源
查看>>
python 学习导图
查看>>
生成树
查看>>
(MYSQL) Unknown table 'a' in MULTI DELETE的解决办法
查看>>
作为一个程序员必备的素质
查看>>
Webpack入门教程十四
查看>>
HDU - 3564 Another LIS(LIS+线段树)
查看>>
深入浅出JavaScript (五) 详解Document.write()方法
查看>>
hibernate简单入门教程(四)---------关联映射
查看>>
去 IOE,MySQL 完胜 PostgreSQL
查看>>
++i 和 i++ 性能上的区别
查看>>
Mysql运维管理-一主多从宕机从库切换主库继续和从库同步过程16
查看>>
Tomcat优化之配置NIO运行模式
查看>>
用XSLT和XML改进Struts
查看>>
WEB测试—功能测试
查看>>
在react或vue中,for循环用Index作为key值是好还是坏呢?
查看>>
2014.10.1 Form中显示pdf文件
查看>>
NERDTree 快捷键辑录
查看>>