1. 组合数取模
求 \(\dbinom nm\bmod p\)
1. \(n,m\le 200\)，\(p\) 任意
递推
2. \(n,m\le 10^6\)，\(p\ge 10^9\) 素数
预处理 \(n!\)，\(m!^{-1}\)，\((n-m)!^{-1}\) 即可 .
3. \(n,m\le 10^6\)，\(p\le 2000\) 素数
注意到 \(n\) 可能是 \(p\) 的倍数，故逆元可能不存在 .
引入 Lucas 定理：
设 \(n,m\) 在 \(p\)（\(p\) 是质数）进制下表示为
\[\overline{n_kn_{k-1}n_{k-2}\dots n_1}\,,\overline{m_km_{k-1}m_{k-2}\dots m_1} \]其中 \(0\le n_i<p\)，\(0\le m_i<p\) .
则有：
\[\dbinom{n}{m}\equiv \dbinom{n_k}{m_k}\dbinom{n_{k-1}}{m_{k-1}}\cdots\dbinom{n_1}{m_1}\pmod p \]
Proof：
原问题等价于 \(C^n_m\equiv C^{n\bmod p}_{m\bmod p}\cdot C^{\lfloor n/p\rfloor}_{\lfloor m/p\rfloor}\pmod p\) .
设 \(x\in\mathbb N^+\)，且 \(x<p\)，则：
\[C^x_p=\dfrac{p!}{x!(p-x)!}=\dfrac{p\cdot (p-1)!}{x\cdot(x-1)!\cdot(p-x)!}=\dfrac px\cdot C^{x-1}_{p-1} \]由于 \(x<p\) 且 \(p\) 是素数，所以 \(x\) 存在模 \(p\) 意义下的逆元，因此：
\[C^x_p\equiv p\cdot x^{-1}\cdot C^{x-1}_{p-1}\pmod p \]因为 \(p\cdot x^{-1}\cdot C^{x-1}_{p-1}\equiv 0\pmod p\) ，故 \(C^x_p\equiv0\pmod p\).
由二项式定理，
\[(1+x)^p=\sum_{i=0}^pC_p^ix_i \]除了 \(i=0,i=p\) 的项数，别的模 \(p\) 均为 \(0\)，所以：
\[(1+x)^p\equiv 1+x^p\pmod p \]现在我们设：
\[\begin{cases}\lfloor m/p\rfloor=q_m\\\lfloor n/p\rfloor=q_n\end{cases}\ ,\ \begin{cases}m\bmod p=r_m\\n\bmod p=r_n\end{cases} \]从而：
\[\begin{cases}m=q_mp+r_m\\n=q_np+r_n\end{cases} \]再由二项式定理有
\[(1+x)^m=\sum_{i=0}^mC_m^ix_i \]而同时又有：
\[\begin{aligned}(1+x)^m&=(1+x)^{q_mp+r_m}\\&=(1+x)^{q_mp}\cdot(q+x)^{r_m}\\&=((1+x)^q)^{m_p}\cdot(q+x)^{r_m}\\&\equiv (1+x^p)^{q_m}\cdot(1+x)^{r_m}\\&=\sum_{i=0}^{q_m}C^i_{q_m}x^{ip}\sum_{i=0}^{r_m}C^i_{r_m}x^{i}\\&=\sum_{i=0}^{q_m}\sum_{j=0}^{r_m}C^i_{q_m}C^j_{r_m}x^{ip+j}\pmod p\end{aligned} \]注意到 \(ip+j\) 正好能取到 \(0\) 到 \(m\) 内所有整数一次，所以枚举 \(k=ip+j\)，得
\[(x+1)^m\equiv \sum_{k=0}^n C_{q_m}^{\lfloor k/p\rfloor}C_{r_m}^{k\bmod p}x^k\pmod p \]结合二项式定理，得
\[\sum_{k=0}^mC^k_mx^k\equiv \sum_{k=0}^n C_{q_m}^{\lfloor k/p\rfloor}C_{r_m}^{k\bmod p}x^k\pmod p \]对比系数，得：
\[C^n_m\equiv C^{n\bmod p}_{m\bmod p}\cdot C^{\lfloor n/p\rfloor}_{\lfloor m/p\rfloor}=C_{q_m}^{q_n}C_{r_m}^{r_n}\pmod p \]命题获证 .
4. \(n,m\le 10^6\)，\(p=p_1p_2\cdots p_k\)，\(p_1,p_2,\cdots,p_k\le 2000\) 为互不相同的素数
令
\[A=\dbinom nm \]则
\[\begin{cases}A\equiv \dbinom nm\bmod p_1\pmod p_1\\A\equiv \dbinom nm\bmod p_2\pmod p_2\\\cdots\\A\equiv \dbinom nm\bmod p_k\pmod p_k\end{cases} \]用 Lucas 定理求组合数，然后 CRT 合并即可