一.CRT
先咕着。
二.Lucas 定理
Lucas 定理是用来求这个东西的：
\[\dbinom{n}{m} \bmod p \]其中 \(p\) 为较小质数。
其结论为：
\[\dbinom{n}{m} \bmod p = \dbinom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p \right\rfloor} \cdot \dbinom{n\bmod p}{m\bmod p} \bmod p \]因为 \(p\) 值较小，\(\binom{n\bmod p}{m\bmod p}\) 可以直接预处理 \(O(1)\) 求解。而 \(\binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p \right\rfloor}\) 可以继续用 Lucas 定理分解递归求解。
证明
首先根据定义可知：
\[\dbinom{p}{n} \bmod p=\dfrac{p!}{n! \cdot (n-p)!} \bmod p \]可以找到性质：仅当 \(n=0 \vee n=p\) 时，该式结果为 \(1\)，否则为 \(0\)。
据此扩展可得：
\[\begin{align} (a+b)^p &= \sum_{n=0}^p \binom pn a^n b^{p-n}\\&\equiv \sum_{n=0}^p [n=0\vee n=p] a^n b^{p-n}\\ &\equiv a^p +b^p \bmod p \end{align} \]最后将其推广到二项式情况，将 \(p\) 提进来即可。
三.扩展 Lucas 定理（exLucas）
恶心东西。不想写。
标签：lfloor,right,dbinom,bmod,全家,rfloor,同余系,Lucas From： https://www.cnblogs.com/victoryang-not-found/p/16603501.html