单位根反演

首先我们有式子：

\[[n \mid m] = \frac{1}{n} \sum_{i=0}^{n-1} \omega_n^{im}\]

证明：设 \(f(x) = \sum_{i=0}^{n-1} x^i\)，那么原式即为 \(f(\omega_n^m)\)。当 \(n \mid m\) 时，求和的每一项都是 \(1\)，显然成立；否则有 \(f(x) = \frac{x^n - 1}{x - 1}\) 成立，由于 \(\omega_n^{nm} = 1\)，故上式为 0。

这个式子可以扩展到 \(m \text{\ mod\ } n = k\) 的情况：

\[[m \text{\ mod\ } n = k] = [n \mid (m - k)] = \frac{1}{n} \sum_{i=0}^{n-1} \omega_n^{-ik} \omega_n^{im}\]

现在有多项式 \(f(x) = \sum_{i=0}^{n} a_i x^i\)，要求其所有下标模 \(m\) 等于 \(k\) 的系数之和，有：

\[\sum_{i=0}^{n} a_i [i \text{\ mod\ } m = k] = \frac{1}{m} \sum_{i=0}^{n} a_i \sum_{j=0}^{m-1} \omega_m^{-jk} \omega_m^{ij}\]

交换求和符号：

\[\frac{1}{m} \sum_{j=0}^{m-1} \omega_m^{-jk} \sum_{i=0}^{n} a_i \omega_m^{ij} = \frac{1}{m} \sum_{j=0}^{m-1} \omega_m^{-jk} f(\omega_m^j)\]

这个式子的优势在于，如果多项式 \(f\) 的次数非常大，但它的点值可以在 \(O(T)\) 的时间复杂度内计算，就可以用上式在 \(O(mT)\) 的时间复杂度内求出 \(f\) 的所有下标模 \(m\) 为 \(k\) 的系数之和。

举个例子，现在要求：

\[\sum_{i=0}^{n} [i \text{\ mod\ } m = k] \binom{n}{i} \text{\ mod\ } p\]

\(n\) 非常大，但 \(m\) 只有 \(10^6\)。由于组合数的 OGF 为 \((1 + x)^n\)，答案即为：

\[\frac{1}{m} \sum_{i=0}^{m-1} \omega^{-ik} (1 + \omega^i)^n\]

如果 \(p \text{\ mod\ } m = 1\)，那么找到 \(p\) 的原根 \(g\)， \(g^{\frac{p-1}{m}}\) 即可作为 \(\omega_m\) 运算，复杂度为 \(O(m \log n)\)。