FFT, NTT 和有关的多项式问题（一）

原根的性质

原根的指数

如果 $g$ 是 $m$ 的原根，那么 $\displaystyle \left<g, g^1, g^2, \cdots, g^{\varphi(m)} \right>$ 形成模 $m$ 的一个简化剩余系
因为 $\displaystyle g^{\varphi(m)} \equiv 1(\bmod \ m)$，实际上
$\displaystyle \left<1, g^1, g^2, \cdots, g^{\varphi(m)-1} \right>$ 形成模 $m$ 的一个简化剩余系

如果 $(a, m) = 1$，那么在区间 $0 \leqslant k \leqslant\varphi(m) - 1$ 中有唯一的 $k$，使得 $\displaystyle a \equiv g^k (\bmod \ m)$
$k$ 称为以 $g$ 为底，$a$ 对模 $m$ 的指数，写为 $\displaystyle k = \text{ind}_g(a)$，也可以写成 $\text{ind}(a)$

指数运算
令 $g$ 是模 $m$ 的一个原根，并且 $(a, m) = (b, m) = 1$，那么有
$\textbf{(1)} \quad \text{ind}(ab) \equiv \text{ind}(a) + \text{ind}(b) (\bmod \ \varphi(m))$

我们有 $\displaystyle g^{\text{ind}(a)} \equiv a(\bmod \ m), \quad g^{\text{ind}(b)} \equiv b(\bmod m)$
由此 $\displaystyle \alpha m + a = g^{\text{ind}(a)}, \ \beta m + b = g^{\text{ind}(b)}$
可以推出 $g^{\text{ind}(a) + \text{ind}(b)} = (\alpha m + a)(\beta m + b) \equiv ab (\bmod m) \equiv g^{\text{ind}(ab)} (\bmod \ m)$
因为 $\text{ind}(ab) \in [0, \varphi(m) - 1]$，我们可以有 $\text{ind}(ab) \equiv \text{ind}(a) + \text{ind}(b) (\bmod \ \varphi(m))$
或者这么看，$\text{ind}(ab)$ 和 $\text{ind}(a) + \text{ind}(b)$ 在 $\varphi(m)$ 的剩余系中相等即可

$\textbf{(2)} \quad \text{ind}(a^n) \equiv n \text{ind}(a) \ (\bmod \ \varphi(m)), \ n \geqslant 1$

同样，$\displaystyle \left( g^{\text{ind}(a)} \right)^n = (a + \alpha m)^n \equiv a^{n} (\bmod \ m) \equiv g^{\text{ind}(a^n)} (\bmod \ m)$

$\textbf{(3)} \quad \text{ind}(1) = 0, \ \text{ind}(g) = 1$

$g^{\text{ind}(g)} \equiv g(\bmod \ m)$，因为 $(g, m) = 1$，所以有 $g^{\text{ind}(g) - 1} \equiv 1 \equiv g^0(\bmod \ m)$
在模 $m$ 的剩余系中，只能 $\text{ind}(g) - 1 = 0$
同样 $1^{\text{ind}(1)} \equiv 1(\bmod \ m)$，所以 $\text{ind}(1)$ 只能是 $0$

$\textbf{(4)} \quad \text{ind}(-1) = \displaystyle \frac{\varphi(m)}{2}, \ m \geqslant 2$

$\displaystyle g^{\frac{ \varphi(m) }{2}} \equiv -1 (\bmod \ m)$，我们不妨来求一下 $g^{\varphi(m) / 2}$，令 $t = \varphi(m) / 2$
$\displaystyle f(g) = \left(g^{t}\right)^2 = g^{\varphi(m)} \equiv 1(\bmod m)$
不妨设 $f(g) = \alpha m + 1$，$f(g)$ 为完全平方数，它只能是 $(km + 1)^2$ 或者是 $(km-1)^2$ 的形式
即 $g^{\varphi(m) / 2} = km + 1$ 或者 $km - 1$，如果 $g^{\varphi(m) / 2} \equiv 1(\bmod \ m)$，与原根定义矛盾
所以只能 $g^{\varphi(m) / 2} \equiv -1(\bmod \ m)$

$\textbf{(5)}$ 如果 $g'$ 也是模 $m$ 的一个原根，那么 $\text{ind}_g(a) \equiv \text{ind}_{g'}(a) \cdot \text{ind}_g(g') \ (\bmod \varphi(m))$

因为 $g'$ 也是模 $m$ 的一个原根，所以有 $g' = g + km$，下面来证明 $\text{ind}_g(g') = 1$
$g^{\text{ind}_g(g')} \equiv g' \equiv (g + km) \equiv g(\bmod \ m)$，因为 $(g, m) = 1$，所以 $\text{ind}_g(g') = 1$

接下来只需要证明 $\text{ind}_g(a) \equiv \text{ind}_{g'}(a)$，考虑 $\displaystyle g^{\text{ind}_g(a)}, \ g^{\text{ind}_g'(a)}$
$\displaystyle g^{\text{ind}_g(a)} \equiv a(\bmod \ m), \ (g')^{\text{ind}_{g'}(a)} \equiv a (\bmod \ m)$
二项展开 $\displaystyle (g')^{\text{ind}_{g'}(a)} = \left(g+km\right)^{\text{ind}_{g'}(a)} \equiv g^{\text{ind}_{g'}(a)}(\bmod m)$

$a \equiv (g')^{\text{ind}_g'(a)} \equiv g^{\text{ind}_g'(a)} \equiv g^{\text{ind}_g(a)} (\bmod \ m)$，证毕

NTT

根据原根理论，对于素数 $p$，如果 $\left<g^1, g^2, g^3, \cdots, g^{p-1} \right>$ 取遍 $\{1, 2, \cdots, p-1 \}$ 的所有整数
那么 $g$ 就是关于素数 $p$ 的原根

这样，在 FFT 中，用 $g_n$ 代替 $\omega_n$，其中 $\displaystyle g_n = g^{\frac{p-1}{n}}$，$n$ 是 $2$ 的幂
那么有如下性质

• $\displaystyle g_n^n = g^{p-1} = g^{\varphi(p)} = 1$
• $\displaystyle g_n^{n/2} = g_n^{(p-1)/2} \equiv -1 (\bmod \ p)$
• $\displaystyle g_{dn}^{dk} = g^{dk(p-1) / dn} = g^{k(p-1) / n} = g_n^{k}$
• $\displaystyle \left(g_n^k \right)^2 = g_{n/2}^k$

这样 FFT 中所有 $\omega_n$ 有的性质，$g_n$ 都有
只不过所有的运算要换成模 $p$ 意义下的运算，$1/n$ 换成模 $p$ 意义下的逆元

剩下的问题就是求原根，常见的模数的原根如下
$p = 1004535809 = 479 \cdot 2^{21} + 1, \quad g = 3$
$p = 998244353 = 7 \cdot 17 \cdot 2^{23} + 1, \quad g = 3$

原根求解算法

假设 $g$ 是关于模 $P$ 的原根，首先 $\displaystyle \left<1, g, g^2, \cdots, g^{\varphi(P) - 1} \right>$ 必须取遍 $P$ 的简化剩余系
那么 $g$ 的取值最坏情况可能是 $\displaystyle \left< 2, 3, \cdots, P-1 \right>$ 这么几种
不难想到可以枚举 $g$

如果 $g$ 不是 $P$ 的原根，那么一定存在 $0 \leqslant i < j \leqslant \varphi(P) - 1$，我们有 $g^i \equiv g^j (\bmod \ P)$
也就是说 $g^{i-j} \equiv 1 (\bmod \ P)$，不妨令 $d = j - i$，我们有
$\displaystyle g^{d} \equiv 1 (\bmod \ P), \quad g^{\varphi(P)} \equiv 1(\bmod \ P)$，从而有 $d \mid \varphi(P)$

于是我们可以想到对 $\varphi(P)$ 进行素因子分解，假设含有的素因子为 $\displaystyle \left<p_1, p_2, \cdots , p_k \right>$
接下来没有必要检查 $\varphi(P)$ 的所有素因子，因为如果我们找到比如说 $d = k \cdot p_i$，使得 $\displaystyle g^{d} \equiv 1 (\bmod \ P)$
那么一定有 $\left< g^{d}, g^{2d}, g^{3d}, \cdots \right> \equiv 1(\bmod \ P)$

所以 $g$ 是原根，那么剔除 $\displaystyle \varphi(P)$ 的任意素因子，即 $\displaystyle d = \left<\frac{\varphi(P)}{p_1}, \frac{\varphi(P)}{p_2}, \cdots \frac{\varphi(P)}{p_k} \right>$

都因该满足 $g^{d} \not \equiv 1(\bmod \ P)$

实现上，可以先预处理对 $\varphi(P) = P-1$ 进行唯一分解，然后枚举 $g \in [2, P-1]$
对于每一个素因子 $\left<p_1, p_2, \cdots, p_k \right>$，如果发现 $\displaystyle g^{\frac{\varphi(P)}{p_i}} \equiv 1(\bmod \ P)$
那么标记 $g$ 不是原根，检查其他的 $g$，否则我们就返回 $g$

NTT 算法实现

一些题目

题目1

染色
算法设计
有 $n$ 个位置需要染色，可以考虑如下分组，先从 $m$ 种颜色中任选 $k$ 种，每一种元素是一组，然后剩下的颜色分一组
对于 $[1\cdots k]$ 组，每一组放 $s$ 个元素，表示 $k$ 种颜色，每一种都染了 $s$ 个位置
那么剩下的呢？剩下 $(n - ks)$ 个位置呢？怎么染色？
实际上，剩下的位置可以染剩下的 $(m - k)$ 种颜色中的任意一种，这样我们可以得到一个初步的表达式

$\displaystyle \binom{m}{k} \cdot (m-k)^{n-ks} \cdot \frac{n!}{(s!)^{k} \cdot (n - ks)!}$

其中 $\displaystyle \frac{n!}{(s!)^k \cdot (n - ks)!}$ 表示分组排列的方案数

但是，这并不是我们需要的，题目中要求有 $k$ 种颜色恰好出现了 $s$ 次
上面的表达式可以保证一定有 $k$ 种颜色出现了 $s$ 次，但是对于剩下的 $(m - k)$ 种颜色呢？
对于未染色的 $(n - ks)$ 个位置，我们是从剩下的 $(m - k)$ 种颜色中任意选取，所以
还可能存在 $k$ 种颜色之外的其他颜色，也染了 $s$ 个位置
上面的表达式计算，求出的出现 $s$ 次的颜色种类 $\geqslant k$ 种，不妨记为 $f(k)$

$\displaystyle f(k) = \binom{m}{k} \cdot (m-k)^{n-ks} \cdot \frac{n!}{(s!)^{k} \cdot (n - ks)!}$

$f(k)$ 表示出现 $s$ 次的颜色至少有 $k$ 种的方案数

我们需要的是出现 $s$ 次的颜色恰好有 $k$ 种的方案，不妨记为 $g(k)$，那么出现 $s$ 次的颜色最多有多少种呢？
不难想到最多有 $\displaystyle N = \min \left(m, \left\lfloor \frac{n}{s} \right\rfloor \right)$

$\displaystyle f(k) = \sum_{i = k}^{N} g(i)$，只可惜这样还是不对

已知出现 $s$ 次的颜色恰好有 $i$ 种，对应的方案数为 $g(i)$，但 $f(k)$ 对应的是
有 $k$ 种颜色一定要出现 $s$ 次，剩下的没有限制，仅仅把 $g(i)$ 加起来会漏解

实际上，对于恰好有 $i$ 种颜色出现 $s$ 次，方案数为 $g(i)$，那么推 $f(k)$ 时应该这样考虑
$i$ 种颜色中 $\displaystyle \binom{i}{k}$ 任意选择 $k$ 种颜色一定出现 $s$ 次，剩下 $(i-k)$ 种颜色出现次数没有限制

$\displaystyle f(k) = \sum_{i = k}^{N} g(i) \cdot \binom{i}{k}$

接下来考虑如何计算，我们需要知道的是 $g(k)$，最后的答案是 $\displaystyle \sum_{k = 0}^{N} (g(k) \cdot w_k)$

$\displaystyle f(k) = \sum_{i = k}^{N} \binom{i}{k} \cdot g(i)$，二项式反演可以得到

$\displaystyle g(k) = \sum_{i = k}^{N} (-1)^{i - k} \binom{i}{k} \cdot f(i)$

化简可得
$\displaystyle k! g(k) = \sum_{i = k}^{N} \left(\frac{(-1)^{i - k}}{(i-k)!} \right) \left(i! f(i) \right)$

令 $A(i) = i! f(i)$，$B(i) = \displaystyle \frac{(-1)^i}{i!}$

那么 $\displaystyle g(k) = \frac{1}{k!} \sum_{i = k}^{N} A(i)B(i-k)$

下面考虑化简该式
$g(k) = \displaystyle \frac{1}{k!} \sum_{k \leqslant i \leqslant N} A(i)B(i-k)$ 并不是标准的卷积形式

做变量替换，令 $i' = i - k$，那么变量范围为 $0 \leqslant i' \leqslant N-k$

$\displaystyle g(k) = \frac{1}{k!} \sum_{0 \leqslant i \leqslant N-k} A(i+k)B(i)$，但可惜这也不是标准卷积形式

令 $A(i+k) = A'(N-k-i)$，这样 $\displaystyle g(k) = \frac{1}{k!} \sum_{0 \leqslant i \leqslant N-k} A'(N-k-i)B(i)$

这就是标准的卷积形式，只要做变换 $A'(x) = A(N-x)$，这样就可以得到

$\displaystyle g(k) = \frac{1}{k!} \sum_{0 \leqslant i \leqslant N-k} A'(N-k-i)B(i)$，用 $\text{NTT}$ 求卷积

int N, n, m, s;
int w[maxm];

void solve() {
    N = min(m, n/s);
    vector<mint> f(N+1, 0);
    for (int i = 0; i <= N; i++) f[i] = binom(m, i) * power(mint(m-i), n-s*i) * fac[n] * power(infac[s], i) * (infac[n-s*i]);
    vector<mint> _a(N+1, 0), _b(N+1, 0);
    for (int i = 0; i <= N; i++) _a[i] = fac[i] * f[i];
    for (int i = 0; i <= N; i++) _b[i] = ( (i & 1) ? (-1) : 1 ) * infac[i];
    for (int i = 0; i <= N; i++) if (i < N - i) swap(_a[i], _a[N-i]);

    Poly A(_a), B(_b);
    Poly C = A * B;

    mint ans = 0;
    for (int k = 0; k <= N; k++) ans = ans + mint(w[k]) * infac[k] * C[N-k];
    printf("%d\n", ans.x);
}

二项式反演的推导（1）

$\displaystyle f_n = \sum_{i = 0}^n \binom{n}{i} g_i \Leftrightarrow g_n = \sum_{i = 0}^{n} (-1)^{n-i} \binom{n}{i} f_i$
这个可以用生成函数来推

$\displaystyle \frac{f_n}{n!} = \sum_{i = 0}^{n} \frac{g_i}{i!} \frac{1}{(n - i)!}$，可以知道

$\displaystyle F = \left\{\frac{f_n}{n!}\right\}$ 的 $\text{EGF}$ 为 $\displaystyle F_i = \sum_{i = 0}^{\infty} f_ix^i$

$\displaystyle G = \left\{\frac{g_n}{n!} \right\}$ 的 $\text{EGF}$ 为 $\displaystyle G_i = \sum_{i = 0}^{\infty} g_ix^i$

根据 $\displaystyle e^x = \sum_{i = 0}^{\infty} \frac{x^i}{i!}, \quad e^{-x} = \sum_{i = 0}^{\infty} (-1)^i \frac{x^i}{i!}$

我们有 $F = G \cdot e^{x}$，由此 $G = F \cdot e^{-x}$，根据生成函数的系数展开

$\displaystyle \frac{g_n}{n!} = \sum_{i = 0}^{n} \frac{f_i}{i!} \cdot (-1)^{n-i} \frac{1}{(n-i)!}$，证毕

二项式反演的推导（2）

$\displaystyle f_n = \sum_{i = 0}^{n} (-1)^i \binom{n}{i}g_i \Longleftrightarrow g_n = \sum_{i = 0}^{n} (-1)^i\binom{n}{i}f_i$

这里使用待定系数的方法来构造

$\displaystyle g_n = \sum_{i = 0}^{n} t(n, i)\cdot f_i, \quad t(n, i)$ 为待定系数

$\displaystyle f_n = \sum_{i = 0}^{n} (-1)^i \binom{n}{i} \sum_{j = 0}^{i} t(i, j)\cdot f_j = \sum_{j = 0}^{n} f_j \sum_{i = j}^{n} (-1)^i \binom{n}{i}t(i, j)$

令 $i' = i - j, \quad i = i'+j$ 代换

$\displaystyle f_n = \sum_{j = 0}^{n} f_j \sum_{i = 0}^{n - j} (-1)^{i+j} \binom{n}{i+j} t(i+j, j)$

注意到 $j = n$ 的时候，$f_n = f_n$，于是我们必须构造出

$\displaystyle [j = n] = \sum_{i = 0}^{n - j} (-1)^{i+j} \binom{n}{i+j} t(i+j, j) \quad \textbf{(1)}$

注意到 $(1-1)^n$ 的展开，有 $\displaystyle [n = 0] = \sum_{i = 0}^{n}(-1)^i \binom{n}{i}$

$\displaystyle [j = n] = \sum_{i = 0}^{n - j} (-1)^i \binom{n - j}{i} \quad \textbf{(2)}$

$\textbf{(1), (2)}$ 对比，可以知道 $t(i+j, j)$ 中有组合数形式，我们配凑

$\displaystyle [j = n] = \sum_{i = 0}^{n - j} (-1)^i \binom{n-j}{i} \binom{n}{j} = \sum_{i = 0}^{n - j} (-1)^i \binom{n}{n - j} \binom{n-j}{i}$

$\displaystyle \quad \quad = \sum_{i = 0}^{n - j} (-1)^i \binom{n}{i} \binom{n-i}{n-j-i} = \sum_{i = 0}^{n - j} (-1)^i \binom{n}{i} \binom{n-i}{j}$

其中，我们根据恒等式 $\displaystyle \binom{n}{i+j} \binom{i+j}{i} = \binom{n}{i} \binom{n-i}{j}$

所以有 $\displaystyle [j = n] = \sum_{i = 0}^{n-j} (-1)^i \binom{n}{i+j} \binom{i+j}{i}$，从而有

$\displaystyle t(i+j, j) = (-1)^j \cdot \binom{i+j}{i} = (-1)^j \binom{i+j}{j}$，从而有

$\displaystyle t(i, j) = (-1)^j \binom{i}{j}$

题目2

城市规划