扩展 Lucas 定理
\(\newcommand{\stirlingI}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}\)Lucas 定理想必大家都知道了:令 \(p\) 为一个质数,\(n = u_1 p + u_2\),\(m = v_2 p + v_2\),其中 \(0 \leq u_2, v_2 < p\),则有
\[
\binom{n}{m} \equiv \binom{u_1}{v_1} \binom{u_2}{v_2} \pmod{p}.
\]
但是 Lucas 定理只对模为质数的情况有效。虽然对于合数我们有 CRT,但是还是得处理模为质数幂的情况。这篇文章主要讲模为质数幂该如何处理。文章非常多的地方参考翻译了 prabowo 的博客(虽然他也是参考了 min_25 的博客),但是也有一些小修改(虽然他也有一些小修改),主要就是改进了一下 bound。
之前 Andrew Granville 也有一篇 关于拓展 Lucas 定理的文章,但是里面特判太多了……复杂度也高,我写过一次之后不想再写了……