Lucas
内容
\[\binom{ap+b}{cp+d}\equiv\binom{a}{c}\binom{b}{d}\pmod{p} \]其中 \(p\) 为素数，\(0\le b,d<p\)，
\[\binom{n}{m}=\frac{n^{\underline m}}{m!} \]推论（重要）
当 \(p=2\) 时有
\[\binom{n}{m}\equiv[m\subseteq n]\pmod{2} \]其中 \(\subseteq\) 表示二进制（相当于状压）的包含。
证明
以下等号均指 \(\bmod p\) 意义下相等。
\[\begin{aligned} \binom{ap+b}{cp+d}&=[x^{cp+d}](x+1)^{ap+b} \\&=[x^{cp+d}]((x+1)^p)^a(x+1)^b \\&=[x^{cp+d}](x^p+1)^a(x+1)^b \\&=([x^{cp}](x^p+1)^a)([x^d](x+1)^b) \\&=([x^c](x+1)^a)([x^d](x+1)^b) \\&=\binom{a}{c}\binom{b}{d} \end{aligned} \] 标签：Lucas,pmod,重修,ap,exLucas,cp,binom,equiv From： https://www.cnblogs.com/shaojia/p/16585470.html