题目

给定 n, m, p，求

杨辉三角递推

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

Solution

根据组合恒等式 可以开一个二维数组 C，其中 C[i][j] 表示 的值。

接下来依次递推即可。

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;
  }

Lucas 定理

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

Solution

Code

根据公式计算