组合数学CSP-S

💡 核心思想

组合数学研究计数问题。核心工具：排列 $A_n^k$、组合 $C_n^k$、杨辉三角、Lucas 定理。在模意义下计算组合数需要预处理阶乘和逆元。$C_n^k = \frac{n!}{k!(n-k)!}$。

🎯 直觉理解

组合数 $C_n^k$ 就是从 $n$ 个人中选 $k$ 个人的选法数。杨辉三角中每个数等于它上方两个数之和——因为"从 $n$ 个人中选 $k$ 个"等于"选了第一个人后从剩下 $n-1$ 个中选 $k-1$ 个"加上"不选第一个人后从剩下 $n-1$ 个中选 $k$ 个"。

📝 算法流程

1. 杨辉三角递推：$C[n][k] = C[n-1][k-1] + C[n-1][k]$
2. 阶乘+逆元：$C_n^k = fac[n] \times inv[k] \times inv[n-k] \mod p$
3. Lucas 定理：$C_n^k \equiv C_{n\mod p}^{k\mod p} \times C_{n/p}^{k/p} \pmod{p}$

$$C_n^k = \frac{n!}{k!(n-k)!}$$

$$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1000005;
ll fac[N], inv[N];
ll qpow(ll a, ll n) { ll ans=1; while(n){if(n&1)ans=ans*a%MOD; a=a*a%MOD; n>>=1;} return ans; }
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
    inv[n] = qpow(fac[n], MOD-2);
    for (int i = n-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
}
ll C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] * inv[k] % MOD * inv[n-k] % MOD;
}
int main() {
    int n, m; cin >> n >> m;
    init(max(n,m));
    cout << C(n, m) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目