排列组合计算方法

题目

给定 $n,m,p$，求
$$ {n\choose m}\bmod p $$

杨辉三角递推

PS：该做法适用于 $p$ 恒定时的做法。

$\textbf{Solution}$

根据组合恒等式
$$ {n\choose m}={n-1\choose m}+{n-1\choose m} $$
可以开一个二维数组 C，其中 C[i][j] 表示 $n\choose m$ 的值。

接下来依次递推即可。

$\textbf{Code}$

1
2
3
4
5
6

// MAX 为最大值
for (int i = 0; i <= MAX; ++i)
  for (int j = 0; j <= i; ++j) {
    if (!j) C[i][j] = 1;
    else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % p;
  }

$\textbf{Lucas}$ 定理

PS：该做法适用于 $p$ 较小时的情况。

$\textbf{Solution}$

$$ {n\choose m} \equiv {\big\lfloor\frac{n}{p}\big\rfloor\choose\big\lfloor\frac{m}{p}\big\rfloor}{n\bmod p\choose m\bmod p}\pmod p $$

$\textbf{Code}$

根据公式计算