LG P3803 【模板】多项式乘法(FFT)
2021/8/13 23:08:39
本文主要是介绍LG P3803 【模板】多项式乘法(FFT),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
贴模板
#include <cstdio> #include <iostream> #include <cmath> #define re register using namespace std; const int N = 2e6 + 1e5; int rev[N], n, m; inline int read() { char ch = getchar(); int f = 1, x = 0; while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = getchar(); while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); return x * f; } const double Pi = acos(-1.0); struct complex{ double x, y; inline complex operator + (const complex &a) const {return complex{x + a.x, y + a.y};} inline complex operator - (const complex &a) const {return complex{x - a.x, y - a.y};} inline complex operator * (const complex &a) const {return complex{x * a.x - y * a.y, x * a.y + y * a.x};} }a[N], b[N]; inline void FFT(complex *a, int lim, int inv) { if (lim == 1) return; for(re int i = 0; i < lim; i++) if (i < rev[i]) swap(a[i], a[rev[i]]); for(re int mid = 1; mid < lim; mid <<= 1) { complex I = complex{cos(Pi / mid), inv * sin(Pi / mid)}; for(re int i = 0; i < lim; i += (mid << 1)) { complex W = complex{1, 0}; for(re int j = 0; j < mid; j++, W = W * I) { complex x = a[i + j], y = W * a[i + j + mid]; a[i + j] = x + y, a[i + j + mid] = x - y; } } } } int main() { n = read(), m = read(); for(re int i = 0; i <= n; i++) a[i].x = read(); for(re int i = 0; i <= m; i++) b[i].x = read(); int limit = 1; while (limit <= n + m) limit <<= 1; int bit = 0; while ((1 << bit) < limit) ++bit; for(re int i = 0; i < limit; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)); FFT(a, limit, 1), FFT(b, limit, 1); for(re int i = 0; i < limit; i++) a[i] = a[i] * b[i]; FFT(a, limit, -1); for(re int i = 0; i <= n + m; i++) printf("%d ", (int)(a[i].x / limit + 0.5)); }
这篇关于LG P3803 【模板】多项式乘法(FFT)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求