二项卷积：

$$ c_n = \sum_k \binom n k a_k b_{n-k} $$

当模数 $M$ 有一质因子 $p\le n$ 时，计算二项卷积无法直接变为 EGF 进行计算，因为 $n!$ 此时不可逆。

我们考虑首先如何解决 $M = p^k$ 时的情况，然后可以用 CRT 合并各情况。

我们记 $v_p(n)$ 是 $n!$ 中 $p$ 的质因子次数，$p$-阶乘为 $n!_p = p^{v_p(n)}$，反 $p$-阶乘为 $\overline{n!_p} = \frac{n!}{n!_p}$。

那么由定义显然 $\overline{n!_p}$ 还是同余 $M$ 可逆的。我们先令 $\widehat a_n = a_n \cdot \left( \overline{n!_p} \right)^{-1} \bmod M$，我们可以得到

$$ \widehat c_n \equiv \sum_k \left(\frac{n!_p}{k!_p (n-k)!_p}\right) \widehat a_k \widehat b_{n-k} \equiv \sum_k p^{v_p(n)-v_p(k)-v_p(n-k)} \widehat a_k \widehat b_{n-k} \pmod M $$

而 $d = v_p(n)-v_p(k)-v_p(n-k)$ 可以推出就是在 $p$ 进制下，$n$ 减去 $k$ 时所发生的退位次数。（这个被叫做 Kummer 定理，过程略）

而 $n$ 在 $p$ 进制下最多只有 $\log_p n$ 位可退，因此我们知道 $p^d \le n$，因此我们在不取模的情况下，可以得到 $\widehat c_n \le n \cdot nM^2 = n^2M^2$。

虽然 $p$ 在模 $M$ 下不可逆，但是当 $p\le n$，自然满足在我们选取的 NTT 模数下都可逆！因此，这一涉及除法的卷积式子，因为已经保证了结果是值域在 $n^2M^2$ 内的整数，所以我们只需选取 NTT 模数进行卷积，之后用 CRT 合并即可。取 $n\le 10^6, M\le 10^9$ 的一般情况下，可得 $c_n \le 10^{30}$，使用四个 NTT 模数进行合并足够。

因此对于每个 $M=p^k$ 的情况，我们都可以通过“四模数 NTT”进行计算，那么对于一般的 $M$ 进行 CRT，算法的复杂度为 $\Theta(n\log n \cdot \omega(M))$，或者也可以解释为，结果值域是 $n^{1+\omega(M)}M^2$ 的卷积。

该提交记录 是一个不算精细的实现。在 $\omega(M)$ 取到最大时大概效率是 loj 的 1s 上下波动（其实这个时候每次 CRT 不用四模数了，如果考虑这一点还能更快）。暂时没想到在“四模数 NTT”的时候避免 int128 的方法。

特殊情况：

• $p$ 很小的时候可以类比子集卷积，加一个占位多项式来帮助计算，但是这个做法的复杂度看起来会带 $p$ 和 $\log_p n$，在 $p$ 大的时候尚未想到能从此想法得到什么优秀的做法。之前思考这个问题的时候也在这里困惑了很久。