原根 (g_n^k)，就是模 p 意义下的单位根，具有与单位根相似的性质，得以用来计算模 p 意义下的多项式乘法，直接套用FFT的式子即可。同时因为要求 n=2^k 且 n \mid p-1，所以 p 都需要可以表示为a\cdot2^k+1 （当然通过中国剩余定理可以做到任意模数多项式乘法(MTT)，这个后面再说）。
#include <bits/stdc++.h>
using namespace std;
const int Mod = 998244353;//Mod = 2 ^ 23 * 119 + 1
const int g = 3, ginv = 332748118;//998244353的一个原根及其逆元
const int MAXN = 2.1e6;
int n, m;
int a[MAXN], b[MAXN];
int rev[MAXN], bit, tot;
inline int qpow(int a, int b) {
int base = a, ans = 1;
while (b) {
if (b & 1) ans = 1ll * ans * base % Mod;
base = 1ll * base * base % Mod;
b >>= 1;
}
return ans;
}
void NTT(int a[], bool inv) {
for (int i = 0; i < tot; i++)
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int len = 1; len < tot; len <<= 1) {
int gn = qpow(inv ? ginv : g, (Mod - 1) / (len << 1));
for (int i = 0; i < tot; i += len * 2) {
int g0 = 1;
for (int j = 0; j < len; j++) {
int x = a[i + j], y = 1ll * g0 * a[i + j + len] % Mod;
a[i + j] = (x + y) % Mod;
a[i + j + len] = (x - y + Mod) % Mod;
g0 = 1ll * g0 * gn % Mod;
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i <= m; i++) scanf("%d", &b[i]);
while ((1 << bit) <= n + m) bit++;
tot = 1 << bit;
for (int i = 1; i < tot; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << bit - 1;
NTT(a, 0), NTT(b, 0);
for (int i = 0; i < tot; i++) a[i] = 1ll * a[i] * b[i] % Mod;
NTT(a, 1);
int inv = qpow(tot, Mod - 2);
for (int i = 0; i <= n + m; i++) printf("%d ", 1ll * a[i] * inv % Mod);// / tot 变为 * inv
return 0;
}
有了乘法，往后就是多项式的各种操作了，尽量只写式子。
以下运算均在模 998244353 意义下进行，如无特殊说明，都有 n \le 10^5 .
\begin{aligned}
F(G-H) &\equiv 0 \pmod {x^{\frac{n}{2}}}\\
G-H &\equiv 0 \pmod {x^{\frac{n}{2}}}\\
(G-H)^2 &\equiv 0 \pmod {x^{n}} \\
H^2 &\equiv 2GH - G^2 \pmod {x^{n}}\\
H &\equiv 2G-FG^2 \pmod {x^{n}}\\
\end{aligned}
在 $O(n \log n)$ 时间内解决。
```cpp
inline void calc_inv(int a[], int n) {//a ← a^(-1) (mod x^n) 多项式求逆
int bas = 1, len = 4, bit = 2;
bool opt = 0;
memset(inv[0], 0, sizeof(inv[0]));
inv[0][0] = qpow(a[0], Mod - 2);
while (bas < n) {
calc_rev(bit, len);
opt ^= 1;
memset(inv[opt], 0, sizeof(inv[opt]));
for (int i = 0; i < bas; i++) inv[opt][i] = 2ll * inv[opt ^ 1][i] % Mod;//bas后面都是0
mul(inv[opt ^ 1], inv[opt ^ 1], len);
mul(inv[opt ^ 1], a, len);
bas <<= 1, len <<= 1, bit++;
for (int i = 0; i < bas; i++) inv[opt][i] = (inv[opt][i] - inv[opt ^ 1][i] + Mod) % Mod;
}
for (int i = 0; i < n; i++) a[i] = inv[opt][i];
}
```
---------------------
## $3)$ 多项式开根 ##
> 给定 $n-1$ 次多项式 $f(x)$，保证常数项为 $1$，求次数 $< n$ 的多项式 $g(x)$，使得 $g^2(x) \equiv f(x) \pmod {x^n}$，多解情况下取常数项较小的作为答案。
显然 $n=1$ 时，$\sqrt F \equiv 1 \pmod x$ .
假设已经求出 $G$，满足 $G^2 \equiv F \pmod {x^\frac{n}{2}}$，目标求出 $H$，使得 $H^2 \equiv F \pmod {x^n}$ .
则
$$
\begin{aligned}
G^2-H^2 &\equiv 0 \pmod {x^\frac{n}{2}}\\
(G-H)(G+H) &\equiv 0 \pmod {x^\frac{n}{2}}\\
\end{aligned}
$$
因为要求常数项最小，即 $1$，所以 $H$ 必然与 $G$ 同余。
即
$$
\begin{aligned}
H-G &\equiv 0 \pmod {x^\frac{n}{2}}\\
H^2-2GH+G^2 &\equiv 0 \pmod {x^{n}}\\
H &\equiv (2G)^{-1}(F+G^2) \pmod {x^{n}}\\
H &\equiv 2^{-1}(G^{-1}F+G) \pmod {x^{n}}
\end{aligned}
$$
结合多项式求逆在 $O(n \log n)$ 时间内解决。
```cpp
inline void calc_sqrt(int a[], int n) {//a ← sqrt(a) (mod x^n)
int bas = 1, bit = 2, len = 4;
bool opt = 0;
memset(sqr[0], 0, sizeof(sqr[0]));
sqr[0][0] = 1;
while (bas < n) {
opt ^= 1;
memset(sqr[opt], 0, sizeof(sqr[opt]));
for (int i = 0; i < bas; i++) sqr[opt][i] = sqr[opt ^ 1][i];
calc_inv(sqr[opt ^ 1], bas << 1);
calc_rev(bit, len);
mul(sqr[opt ^ 1], a, len);
bas <<= 1, len <<= 1, bit++;
for (int i = 0; i < bas; i++) sqr[opt][i] = 1ll * inv2 * (sqr[opt ^ 1][i] + sqr[opt][i]) % Mod;
}
for (int i = 0; i < n; i++) a[i] = sqr[opt][i];
}
```
---------------------
## $4)$ 多项式取模 ##
先介绍一个概念，假设我们有多项式 $f(x)=\{a_0,a_1,...,a_{n-1},a_n\}$，那么我们将 $\{a_n,a_{n-1},...,a_1,a_0\}$ 称为 $f(x)$ 的反射多项式，记作 $F^R$。
显然我们有：
$$f(x)=x^nf(\frac{1}{x})$$
进入正题。
> 给定 $n-1$ 次多项式 $f(x)$，与 $m-1$ 次多项式 $g(x)$，求多项式 $h(x),r(x)$，满足：
> - $h(x)$ 次数为 $n-m$，$r(x)$ 次数 $<m-1$ .
> - $F=GH+R$ .
不妨设 $R$ 的次数为 $m-2$， 那么有
$$
\begin{aligned}
F&=GH+R\\
x^{n-1}F&=x^{m-1}G * x^{n-m}H+x^{n-m+1}x^{m-2}R\\
F^R&=G^RH^R+x^{n-m+1}R^R\\
F^R &\equiv G^RH^R \pmod {x^{n-m+1}}\\
H^R &\equiv F^R(G^R)^{-1} \pmod {x^{n-m+1}}\\
\end{aligned}
$$
结合多项式求逆在 $O(n \log n)$ 时间内解决，最后 $R=F-GH$ 求出 $R$ 即可。
```cpp
inline void division(int a[], int n, int b[], int m) {
for (int i = 0; i < n; i++) ta[i] = a[n - i - 1];
for (int i = 0; i < m; i++) tb[i] = b[m - i - 1];
calc_inv(tb, n - m + 1);
int len = 1, bit = 0;
while (len < n - m + 1 << 1) len <<= 1, bit++;
calc_rev(bit, len);
mul(ta, tb, len);
reverse(ta, ta + n - m + 1);
for (int i = 0; i < n - m + 1; i++) printf("%d ", ta[i]); puts("");
len = 1, bit = 0;
while (len < m << 1) len <<= 1, bit++;
for (int i = n - m + 1; i < len; i++) ta[i] = 0;
calc_rev(bit, len);
mul(b, ta, len);
for (int i = 0; i < m - 1; i++) printf("%d ", (a[i] - b[i] + Mod) % Mod);
}
```
---------------------
## $5)$ 多项式 $\ln$ ##
首先我们要知道几个式子：
- 若 $f(x)= \ln x$，则 $f'(x)= \dfrac{1}{x}$ . （自然对数函数求导）
- 若 $f(x)= k \cdot x^a$，则 $f'(x)= ka \cdot x^{a-1}$ . （幂函数求导）
- 若 $f(x)= k \cdot x^a$，则 $\int f(x)dx= \frac{k}{a+1}x^{a+1}+C$ . （幂函数求积）
- 若 $f(x)= g(h(x))$，则 $f'(x)=g'(h(x))h'(x)$ . （链式法则）
另外，对多项式求导（求积）等于对各个单项式求导（求积）后再加起来。
进入正题：
> 给定 $n-1$ 次多项式 $f(x)$，求多项式 $g(x)$，满足 $g(x) \equiv \ln f(x) \pmod {x^n}$，保证 $[x^0]F=1$ .
> $\ln (1-f(x)) = - \sum_{i=0}^{+ \infty} \frac{f^i(x)}{i}
根据上面的式子，我们有：
\begin{aligned}
G &\equiv \ln F \pmod {x^n}\\
G' &\equiv F'F^{-1} \pmod {x^n} \\
G &\equiv \int F'F^{-1} \pmod {x^n}
\end{aligned}
结合多项式求逆在 O(n \log n) 时间内解决。
void ln(int a[], int n) {
memset(ta, 0, sizeof(ta));
for (int i = 1; i < n; i++) ta[i - 1] = 1ll * a[i] * i % Mod;
calc_inv(a, n);
int len = 1, bit = 0;
while (len < n << 1) len <<= 1, bit++;
calc_rev(bit, len);
mul(a, ta, len);
for (int i = n - 1; i; i--) a[i] = 1ll * a[i - 1] * qpow(i, Mod - 2) % Mod;
}