# 组合数求法

# 方法一 ：动态规划（取模值）

利用组合数公式：$C^{b}_{a} = C^{b}_{a - 1} + C^{b - 1}_{a - 1}$ 进行状态转移.

• 对于$C^{b}_{a} = C^{b}_{a - 1} + C^{b - 1}_{a - 1}$ 的理解:

  $C^{b}_{a}$ 的数学含义：从有$a$ 个小球的箱子中随机抽$b$ 个小球的方案数.
  $\Leftrightarrow$ 1. 先从箱子中选一个小球，那么还需要从$a-1$ 个小球中选$b-1$ 个小球，方案数为$C^{b - 1}_{a - 1}$. 2. 先从箱子中选一个小球扔掉，那么还需要从$a-1$ 个小球中选$b$ 个小球，方案数为C^{b}_

求解$C^{b}_{a}$ 的值，结果对$10^{9}-7$ 取模.

int f[N][N], MOD = 1E9 + 7;

void getCombination(int n){

    for(int i = 0; i <= n; i ++ )	f[i][0] = 1;  // 初始化 C_{a=i}_{b=0} = 1

    for(int i = 1; i <= n; i ++ )

        for(int j = 1; j <= i; j ++ )

            f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;

}

• 时间复杂度：$O(n^{2})$
• 空间复杂度：$O(n^{2})$

运用场景：可以通过预处理求出$C_{a}^{b}$ 范围内的所有组合数，然后通过$O(1)$ 时间复杂度求出该组合数.
局限性：当$a$ 很大时，预处理的时间和空间的复杂度都无法接受

相关题目：

• 885. 求组合数 I

# 方法二：费马小定理 + 快速幂（取模值）

利用组合数公式：$C_{a}^{b}=\frac{a(a-1)\cdots(a-b+1)}{b!}= \frac{a(a - 1) \cdots (a-b+1) \times (a-b)!}{b!(a-b)!}=\frac{a!}{b!(a-b)!}$.

1. 预处理出所以$n!$
2. 利用费马小定理：$C_{a}^{b}\,(mod\;p)=\frac{a!}{b!(a-b)!}\,(mod\;p)=a!\times inv[b!(a-b)!]$，其中$inv(b!(a-b)!)$ 指代$b!(a-b)!$ 关于$p$ 的逆元
3. 通过快速幂求解逆元

constexpr int N = 1e5 + 10, MOD = 1E9 + 7;

ll f[N]; 	/* f[i]: i! % MOD */

ll qmi(ll a, ll b, ll q){

    ll res = 1;

    while(b){

        if(b & 1)   res = res * a % q;

        b >>= 1;

        a = a * a % q;

    }

    return res;

}

int C(int a, int b){

    return f[a] * qmi(f[b] * f[a - b] % MOD, MOD - 2, MOD) % MOD;

}

/*-----------------------------------------------*/

// 预处理阶乘

int main(){

    f[0] = 1;

	for(int i = 1; i <= N - 1; i ++ )   f[i] = f[i - 1] * i % MOD;

    int a, b;	cin >> a >> b;

    cout << C(a, b) << endl;

    return 0;

}

• 时间复杂度：预处理阶乘$O(n)$， 求解组合数$O(logn)$
• 空间复杂度：存储阶乘数组$O(n)$

局限性：当$a$ 超大时，预处理的时间和空间的复杂度都无法接受，例如$a>10^{9}$.

相关题目：

• 886. 求组合数 II

# 方法三：Lucas（卢卡斯） 定理（取模值）

# 定义

Lucas 定理内容如下：对于质数$p$ ，有：

$$C_{a}^{b}\;(mod \; p)=C_{\lfloor a/p \rfloor}^{\lfloor b/p \rfloor}\cdot C_{a\%p}^{b\%p}\;(mod \; p)$$

# 证明

• 证明一：$C_{p}^{m}\,(mod\;p)\equiv0(p为质素)$，其中$m<p且m>0$

  $C_{p}^{m}\,(mod\;p)=\frac{p!}{m!(p-m)!}\,(mod\;p)=\frac{p}{m} \cdot \frac{(p-1)!}{(m-1)!(p-m)!}\,(mod\;p)=\frac{p}{m}C_{p-1}^{m-1}\,(mod\;p)$.

  由于$m<p$ 且$p$ 为质数，固$m$ 关于$p$ 的逆元$inv(m)$ 一定存在.

  $\therefore C_{p}^{m}\,(mod\;p)=p\cdot inv(m) \cdot C_{p-1}^{m-1}\,(mod\;p)=0$ 得证.

• 证明二：结论证明

  求解$C_{a}^{b}\Leftrightarrow$ 求解$(1+x)^{a}$ 的$x^{b}$ 的系数.

  不妨设$q_{a}=\lfloor a/p \rfloor, r_{a}=a\%p$，易知$r_{a}<p$.

  由于$(1+x)^{a}=(1+x)^{q_{a}\cdot p + r_{a}}=[(1+x)^{p}]^{q_{a}} \cdot (1+x)^{r_{a}}$

  又由证明一\Rightarrow (1+x)^{p}\,(mod\;p)=\sum_{i=0}^{p}C_{p}^{i}x^{i}\,(mod\;p)=1+x^

  $\therefore (1+x)^{a}=(1+x^p)^{q_{a}} \cdot (1+x)^{r_{a}}$

  不妨设$q_{b}=\lfloor b/p \rfloor, r_{b}=b\%p$，易知$r_{b}<p$.

  \Rightarrow C_{a}^

# 方法四：高精度（准确值）