Power oj 2540 (FFT卷积)
发布日期:2021-06-29 21:40:30
浏览次数:2
分类:技术文章
本文共 2144 字,大约阅读时间需要 7 分钟。
题目链接:https://www.oj.swust.edu.cn/problem/show/2540
代码:
#include<bits/stdc++.h>
using namespace std; const int FFT_MAXN = 1 << 18; const double pi = acos(-1.0); struct Complex { double R, I; inline Complex(double real = 0.0, double image = 0.0) { R = real, I = image; } inline Complex operator + (Complex const &b) const { return Complex(R + b.R, I + b.I); } inline Complex operator - (Complex const &b) const { return Complex(R - b.R, I - b.I); } inline Complex operator * (Complex const &b) const { return Complex(R * b.R - I * b.I, I * b.R + R * b.I); } } Wn[FFT_MAXN + 1]; int bitrev[FFT_MAXN]; inline int getLength(int n, int m) { n = n + m - 1; int i = 1; for(; i < n; i <<= 1); return i; } void Change(Complex a[], int n) { int d = 0; while((1 << d)*n != FFT_MAXN) d++; for(int i = 0; i < n; i++) if(i < (bitrev[i] >> d)) swap(a[i], a[bitrev[i] >> d]); } void FFT(Complex P[], int n, int op) { Change(P, n); for(int len = 2; len <= n; len <<= 1) { int m = len >> 1; int del = FFT_MAXN / len * op; for(int i = 0; i < n; i += len) { Complex *p = P + i, *q = P + i + m, *w = op == 1 ? Wn : Wn + FFT_MAXN; for(int j = 0; j < m; j++, p++, q++, w += del) { Complex ne = *q * *w; *q = *p - ne; *p = *p + ne; } } } if(op == -1) for(int i = 0; i < n; i++) { P[i].R /= n; P[i].I /= n; } } void FFTInit() { int L = 0; while((1 << L) != FFT_MAXN) L++; bitrev[0] = 0; for(int i = 1; i < FFT_MAXN; i++) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1)); for(int i = 0; i <= FFT_MAXN; i++) Wn[i] = Complex(cos(2 * pi / FFT_MAXN * i), sin(2 * pi / FFT_MAXN * i)); } Complex A[FFT_MAXN], B[FFT_MAXN]; int main() { FFTInit(); int n, m; scanf("%d%d", &n, &m); int N = getLength(n, m); for(int i = 0; i < N; i++) { if(i < n) { int x; scanf("%d", &x); A[i] = Complex(x, 0); } else A[i] = Complex(); } for(int i = 0; i < N; i++) { if(i < m) { int y; scanf("%d", &y); B[i] = Complex(y, 0); } else B[i] = Complex(); } FFT(A, N, 1); FFT(B, N, 1); for(int i = 0; i < N; i++) A[i] = A[i] * B[i]; FFT(A, N, -1); for(int i = 0; i <= n + m - 2; i++) { if(i == 0) printf("%d", (int)(A[i].R+0.5 )); else printf(" %d", (int)(A[i].R+0.5)); } printf("\n"); return 0; }
转载地址:https://dh-butterfly.blog.csdn.net/article/details/77451746 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月16日 12时28分37秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C# EF添加ADO.NET实体数据模型时,产生.Desiger.cs文件为空
2019-04-30
C#利用反射和泛型给不同对象赋值
2019-04-30
C# 对象互转
2019-04-30
C# EntityCollection 和 List 互转
2019-04-30
c# xml序列化和反序列化
2019-04-30
visual studio code download url
2019-04-30
C# 注册windows 服务
2019-04-30
C# wsdl.exe 生成类文件
2019-04-30
C#类型转换工具类
2019-04-30
C# DataTable和List转换操作类
2019-04-30
C#xml泛型序列化
2019-04-30
C#获取客户端Ip工具类
2019-04-30
C#记录日志到本地文件工具类
2019-04-30
C#对象转换工具类
2019-04-30
C# SHA512和Base64加解密方法
2019-04-30
vs professional 2019 离线安装包下载方法
2019-04-30
sit、qas、dev、pet
2019-04-30
C# json转对象
2019-04-30
js定时器
2019-04-30
Jenkins 2017年用过
2019-04-30