..
Kummer's theorem
定理：
Kummer’s theorem 指出，對於給定的非負整數 $n\geq m \geq 0$ 和素數 $p$，則 $v_p\left(C_n^m\right)$ 等於以 $p$ 為基底時 $m$ 加上 $(n - m)$ 的進位次數。
證明：
由於 $C_{n+m}^m$ 所含 $p$ 的幂次為：
\[\begin{align*} &\sum_{i=1}^{\infty}\left[\frac{m+n}{p^i}\right]-\sum_{i=1}^{\infty}\left[\frac{n}{p^i}\right]-\sum_{i=1}^{\infty}\left[\frac{m}{p^i}\right]\\ =&\sum_{i=1}^{\infty}\left[\frac{m+n}{p^i}\right]-\left[\frac{n}{p^i}\right]-\left[\frac{m}{p^i}\right] \end{align*}\]可以發現：
\[\sum_{i=1}^{\infty}\left[\frac{m+n}{p^i}\right]-\left[\frac{n}{p^i}\right]-\left[\frac{m}{p^i}\right]= \begin{cases} 1\text{在 (i+1) 位發生進位}\\ 0\text{在 (i+1) 位不發生進位} \end{cases}\]故求和後就是 $m+n$ 在 $p$ 進制下進位的次數。
典例：
2018-2019 9th BSUIR Open Programming Championship. Final C. Partial Sums
首先有
\[A_{k}[i,j]=\left(\sum_{u,v}A_0[u,v]C_{i-u+k-1}^{i-u}C_{j-v+k-1}^{j-v}\right)\mod 2\]故當 $2^d\geq \max(n, m)$ 時，只有 $A_0[i,j]$ 才有貢獻，故 $2^d$ 必為 $A$ 的一个循環節，故其階（最小循環節）為 $2^t(t\leq d)$。接着暴力枚舉檢驗就好了。
複雜度：$O(nm\log(\max(n,m)))$。
XX Open Cup, Grand Prix of Tokyo E. Count Modulo 2
即求：
\[\begin{align*} &\sum_{i=1}^{k}A_ib_i=S\\ &\sum_{i=1}^{k}b_i=n \end{align*}\]其中 $b_i\geq 0$ 的情況數的奇偶。根据 Kummer’s theorem，$b_i$ 之或為 $n$ 且 $b_i$ 两两與為 $0$。所以可按位對 $n$ 進行動態規劃。另外記 $\max(A_i)=V$，則第 $i$ 位做完的值必不超過 $V2^i$，且遮裏面祇有 $\mod 2^{i-1}$ 與 $S$ 同餘的狀態有貢獻，所以 $S$ 也拆位同時做，不斷篩去不合法的，然後留給下一次 dp 的狀態就祇有 $O(V)$ 个，最後 $f[0]$ 的奇偶性就是答案。但最後要用 bitset 加速。
複雜度：$O(TKV\log(S)/\omega)$。