FFT / NTT 快速傅里叶/数论变换模板 / P3803

前言

FFT是很优美的一个方法，可以解决多项式中的许多问题，NTT则是在模p意义下的多项式乘积， 两者十分相似，所不同的是两者所在数域的单位根不同， 一个是 ω = e 2 π n i \omega = e^{\frac{2\pi }{n}i} ω=en2π​i，另一个是 g , ( p ∤ g i , ∀ i ) g,(p\nmid g^i,\forall i) g,(p∤gi,∀i) 下面给出非递归的代码模板，用到了二进制位逆序变换、蝴蝶操作 值得注意的是，遇见1004535809和998244353要敏感些，极大可能就是NTT的题

一、例题

题目链接 洛谷-P3803

二、思路及代码 1.思路

很单纯的一道FFT/NTT，直接套模板

2.代码

FFT版本：

#include 
#include 
#define int long long
#define pi acos(-1.0)
using namespace std;
const int maxn = 1e7 + 7;
int n, m;
int N, len;
int rev[maxn];
struct complex {
  double r, i;
  complex() {}
  complex(double a, double b) : r(a), i(b) {}
} a[maxn], b[maxn], ans[maxn];
complex operator+(const complex a, const complex b) {
  return complex(a.r + b.r, a.i + b.i);
}
complex operator-(const complex a, const complex b) {
  return complex(a.r - b.r, a.i - b.i);
}
complex operator*(const complex a, const complex b) {
  return complex(a.r * b.r - a.i * b.i, a.i * b.r + a.r * b.i);
}
void FFT(complex a[], int inv) {
  for (int i = 0; i  0 4 2 6 1 5 3 7
    if (i