题目大意:$FFT$,给你两个多项式,请输出乘起来后的多项式。

题解:$FFT$,由于给的$n$不是很大,也可以用$NTT$做

卡点:

C++ Code:

 FFT:

#include <cstdio>
#include <cmath>
using namespace std;
const double Pi = acos(-1);
int n, m;
struct complex {
double r, i;
complex (double a = 0, double b = 0) {r = a, i = b;}
complex operator + (complex a) {return (complex) {r + a.r, i + a.i};}
complex operator - (complex a) {return (complex) {r - a.r, i - a.i};}
complex operator /= (int a) {r /= a, i /= a;}
complex operator * (complex a) {return (complex) {r * a.r - i * a.i, r * a.i + i * a.r};}
} a[500000], b[500000];
int rev[500000], dig, l;
void swap(complex &a, complex &b) {complex t = a; a = b; b = t;}
void FFT(complex *a, int op) {
for (int i = 0; i < l; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int mid = 1; mid < l; mid <<= 1 ) {
complex Wn(cos(Pi / mid), op * sin(Pi / mid));
for (int i = 0; i < l; i += (mid << 1)) {
complex W(1, 0);
for (int j = 0; j < mid; j++, W = W * Wn) {
complex X = a[i + j], Y = W * a[i + j + mid];
a[i + j] = X + Y;
a[i + j + mid] = X - Y;
}
}
}
if (op == -1) for (int i = 0; i <= l; i++) a[i] /= l;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) scanf("%lf", &a[i].r);
for (int i = 0; i <= m; i++) scanf("%lf", &b[i].r);
l = 1; while (l <= (n + m)) l <<= 1, dig++;
for (int i = 0; i < l; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (dig - 1));
FFT(a, 1), FFT(b, 1);
for (int i = 0; i < l; i++) a[i] = a[i] * b[i];
FFT(a, -1);
for (int i = 0; i <= n + m; i++) printf("%d ", int(a[i].r + 0.5));
return 0;
}

NTT:

#include <cstdio>
#define int long long
using namespace std;
const int maxn = 2100010;
const int mod = 998244353;
const int P = 3, invP = 332748118;
int n, m;
int a[maxn], b[maxn], rev[maxn], l, dig;
int Inv[2040826], invl;
inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}
int inv(int i) {
if (i < 2040826) {
if (Inv[i]) return Inv[i];
return (Inv[i] = inv(mod % i) * (mod - mod / i) % mod);
}else return inv(mod % i) * (mod - mod / i) % mod;
}
inline int pw(int base, int p) {
int ans = 1;
for (p <<= 1; p >>= 1; (base *= base) %= mod) if (p & 1) (ans *= base) %= mod;
return ans;
}
void NTT(int *a, int op) {
int Yx;
if (op == 1) Yx = P; else Yx = invP;
for (int i = 0; i < l; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int mid = 1; mid < l; mid <<= 1) {
int Wn = pw(Yx, (mod - 1) / (mid << 1));
for (int i = 0; i < l; i += (mid << 1)) {
int W = 1;
for (int j = 0; j < mid; j++, W = W * Wn % mod) {
int X = a[i + j], Y = W * a[i + j + mid] % mod;
a[i + j] = (X + Y) % mod;
a[i + j + mid] = (X - Y + mod) % mod;
}
}
}
if (op == -1) for (int i = 0; i < l; i++) a[i] = (a[i] * invl) % mod;
}
signed main() {
Inv[0] = Inv[1] = 1;
scanf("%lld%lld", &n, &m);
for (int i = 0; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 0; i <= m; i++) scanf("%lld", &b[i]);
l = 1; while (l <= n + m) l <<= 1, dig++; invl = inv(l);
for (int i = 1; i < l; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (dig - 1));
NTT(a, 1), NTT(b, 1);
for (int i = 0; i < l; i++) (a[i] *= b[i]) %= mod;
NTT(a, -1);
for (int i = 0; i <= n + m; i++) printf("%lld ", a[i]);
return 0;
}

  

  

  

最新文章

  1. ASP.NET Web.config
  2. chrome的自动缓存真是讨厌。
  3. 轻松搭建Unity3D 安卓Android开发环境
  4. c语言结构体小知识
  5. 03server平台delphi程序不支持直接调用webservice
  6. 在CentOS上为DiscuzX3安装ImageMagick支持。
  7. 【转】Flask快速入门
  8. [React] React Router: Named Components
  9. OpenStack high-level Functionsenabled
  10. linux 细节 问题解决
  11. 常用按钮css
  12. 解决error while loading shared libraries的通用方案
  13. (light oj 1024) Eid (最小公倍数)
  14. javascript 零碎笔记
  15. git关联远程仓库
  16. 百度地图API---JS开发
  17. poj2774
  18. 5. MIZ7035 PCIe测试 RIFFA【PCIE视频传输】
  19. iOS开发总结
  20. cent7.0 mysql 修改端口

热门文章

  1. JetBrains PyCharm 2017.3注册码
  2. cnpm 下载
  3. 微信小程序之公共组件写法
  4. 21.1 XMLHttpRequest 对象【JavaScript高级程序设计第三版】
  5. 使用virtual安装Windows系列操作系统总结
  6. Python基本数据类型(一)
  7. Java学习笔记八:Java的流程控制语句之循环语句
  8. 解决软件启动报error while loading shared libraries: libgd.so.2: cannot open shared object错误
  9. Kubernetes-apiserver
  10. 成都Uber优步司机奖励政策(3月25日)