符号与约定
若无特殊说明，多项式的大小均默认为 \(n=2^k\)。
我们定义 \([x^i]F(x)\) 表示 \(F(x)\) 的第 \(i\) 项系数，其中 \(F(x)\) 为多项式。那么有 \(F(x)=\displaystyle\sum_{i=0}^{n-1}[x^i]F(x)\cdot x^i\)。
我们使用 \(F(x)\bmod x^n\) 来限定 \(F(x)\) 的次数上界，例如 \((x^2+2x+1)\bmod x^2=2x+1\)。显然模 \(x^n\) 的多项式域对加减乘封闭（因为只会从低位转移到高位）
基础模板
const int kM = 998244353;
struct Mi {
int v;
Mi(LL v = 0) : v((v % kM + kM) % kM) {}
Mi operator=(LL v) { return *this = Mi(v); }
Mi operator+(const Mi &o) const { return Mi(v + o.v); }
Mi operator-(const Mi &o) const { return Mi(v - o.v); }
Mi operator*(const Mi &o) const { return Mi(1LL * v * o.v); }
Mi operator~() const;
Mi operator/(const Mi &o) const { return *this * ~o; }
Mi operator+=(const Mi &o) { return *this = *this + o; }
Mi operator-=(const Mi &o) { return *this = *this - o; }
Mi operator*=(const Mi &o) { return *this = *this * o; }
Mi operator/=(const Mi &o) { return *this = *this / o; }
};
istream &operator>>(istream &in, Mi &o) {
LL v;
in >> v;
o = v;
return in;
}
ostream &operator<<(ostream &out, const Mi &o) { return out << o.v; }
Mi P(Mi b, LL e) {
Mi s = 1;
for (; e; e >>= 1, b *= b) {
if (e & 1) {
s *= b;
}
}
return s;
}
Mi Mi::operator~() const { return P(this->v, kM - 2); }
const Mi kG = 3, kiG = ~kG;
using Poly = vector<Mi>;
int Scale(int n) {
int l = 1;
for (; l < n; l <<= 1) {
}
return l;
}
const int kL = 22;
Mi kO[kL], kiO[kL];
int _Init_omega = []() {
for (int i = 0; i < kL; ++i) {
kO[i] = P(kG, (kM - 1) / (1 << i));
kiO[i] = P(kiG, (kM - 1) / (1 << i));
}
return 0;
}();
int kBr[1 << kL];
void InitBr(int n) {
for (int i = 0; i < n; ++i) {
kBr[i] = kBr[i >> 1] >> 1 | (i & 1) * (n / 2);
}
}
int mxn;
void Init(int mx) {
mxn = Scale(mx);
InitBr(mxn);
}
加与减
多项式乘法/卷积
详见我的 深入理解 FFT。
知周所众，浮点运算 \(\approx\) 精度误差+大常熟，所以拉了/ruo。
考虑在模意义下能够替代单位根的东西。
可以发现，原根的性质和单位根很像，设 \(g\) 是某个模数的原根，那么可以发现 \(g^k\) 的阶数即为 \(\dfrac{p-1}{\gcd(k,p-1)}\)，即 \(g^k=\omega_{(p-1)/\gcd(k,p-1)}\)，代入 \(k=(p-1)/n\) 可得 \(g^{(p-1)/n}=\omega_{(p-1)/\gcd((p-1)/n,p-1)}=\omega_{(p-1)/((p-1)/n)}=\omega_n\)。由于我们默认 \(n=2^k\)，我们只需要让模数 \(p\) 形如 \(2^k\cdot r+1\)，其中 \(k\) 是个不小的数即可。经典模数 \(998244353=2^{23}\times 7\times 17+1\) 就符合此条件。
void NTT(const Poly &a, Poly &b, bool iv) {
int n = a.size();
b.resize(n);
for (int i = 0; i < n; ++i) {
b[i] = a[kBr[i]];
}
for (int l = 1, c = 0; l < n; l <<= 1, ++c) {
Mi bo = (iv ? kiO : kO)[c + 1], so = 1;
for (int i = 0; i < l; ++i) {
for (int j = 0; j < n; j += l << 1) {
Mi v = so * b[j + l + i];
b[j + l + i] = b[j + i] - v;
b[j + i] += v;
}
so *= bo;
}
}
if (iv) {
for (Mi &v : b) {
v /= n;
}
}
}
void iNTT(Poly &a, bool iv) {
Poly b;
NTT(a, b, iv);
a = b;
}
Poly operator|(const Poly &x, const Poly &y) {
Poly s = x;
for (int i = 0; i < x.size(); ++i) {
s[i] *= y[i];
}
return s;
}
Poly operator*(const Poly &x, const Poly &y) {
Poly _x, _y;
NTT(x, _x, 0), NTT(y, _y, 0);
NTT(_x | _y, _x, 1);
return _x;
}
多项式求逆
我们有这样一个问题：给定 \(F(x)\)，求一个多项式 \(G(x)\) 使得 \(F(x)\times G(x)\equiv 1\pmod {x^n}\)。
考虑对界进行倍增，边界情况为 \(F(x)\times G(x)\equiv 1\pmod{x}\)，此时对 \(F(x)\) 的常数项取逆即可。
假设我们现在已经知道了 \(G'(x)\equiv F(x)^{-1}\pmod{x^{n/2}}\)，设 \(G(x)\equiv F(x)^{-1}\pmod{x^n}\)，显然有 \(G(x)\equiv G'(x)\pmod{x^{n/2}}\)，于是有：