组合计数进阶

概念讲解

Lucas 定理

用于计算大组合数取模。

Cnmmod  p=Cn/pm/p⋅Cnmod  pmmod  pmod  pC_n^m \mod p = C_{n/p}^{m/p} \cdot C_{n \mod p}^{m \mod p} \mod p

卡特兰数

Cn=C2nnn+1C_n = \frac{C_{2n}^n}{n+1}

Burnside/Polya 计数

用于计算在对称性下的不同方案数。

实现

Lucas 定理

1234int lucas(long long n, long long m, int p) {
    if (m == 0) return 1;
    return lucas(n / p, m / p, p) * C(n % p, m % p) % p;
}

卡特兰数

123456789const int MOD = 1e9 + 7;
int catalan[1000005];

void init(int n) {
    catalan[0] = 1;
    for (int i = 1; i <= n; i++) {
        catalan[i] = catalan[i-1] * (4 * i - 2) % MOD * inv(i + 1) % MOD;
    }
}

应用场景

1. 大组合数取模

1int result = lucas(n, m, p);

2. 括号序列计数

n 对括号的合法序列数 = 卡特兰数 C_n

3. 凸多边形三角剖分

n+2 边凸多边形的三角剖分数 = 卡特兰数 C_n

考点分析

初赛考查方式

  1. 选择题： 组合计数的概念
  2. 程序阅读： 理解组合计数
  3. 编程题： 组合计数应用

常见题型

  • 大组合数取模
  • 卡特兰数
  • 对称性计数

例题精讲

例题 1：大组合数取模

题目： 求 C(n, m) mod p。

解答：

12345678910111213141516171819202122232425262728293031323334353637383940#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;

int quickPowerMod(int a, int n, int mod) {
    int result = 1;
    a %= mod;
    while (n > 0) {
        if (n % 2 == 1) result = result * a % mod;
        a = a * a % mod;
        n /= 2;
    }
    return result;
}

int C(int n, int m) {
    if (m < 0 || m > n) return 0;
    
    int result = 1;
    for (int i = 0; i < m; i++) {
        result = result * (n - i) % MOD * quickPowerMod(i + 1, MOD - 2, MOD) % MOD;
    }
    
    return result;
}

int lucas(long long n, long long m, int p) {
    if (m == 0) return 1;
    return lucas(n / p, m / p, p) * C(n % p, m % p) % p;
}

int main() {
    long long n, m;
    cin >> n >> m;
    
    cout << lucas(n, m, MOD) << endl;
    
    return 0;
}

练习题

  1. 洛谷 P3807 Lucas 定理
查看答案

思路：Lucas 定理模板题。

1234567891011121314151617181920212223242526272829303132333435363738394041424344#include <iostream>
using namespace std;

int quickPowerMod(int a, int n, int mod) {
    int result = 1;
    a %= mod;
    while (n > 0) {
        if (n % 2 == 1) result = (long long)result * a % mod;
        a = (long long)a * a % mod;
        n /= 2;
    }
    return result;
}

int C(int n, int m, int p) {
    if (m < 0 || m > n) return 0;
    
    int result = 1;
    for (int i = 0; i < m; i++) {
        result = (long long)result * (n - i) % p * quickPowerMod(i + 1, p - 2, p) % p;
    }
    
    return result;
}

int lucas(long long n, long long m, int p) {
    if (m == 0) return 1;
    return (long long)lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        long long n, m;
        int p;
        cin >> n >> m >> p;
        
        cout << lucas(n + m, n, p) << endl;
    }
    
    return 0;
}
  1. 洛谷 P1044 栈
查看答案

思路：卡特兰数。

12345678910111213141516#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    long long catalan[n + 1];
    catalan[0] = 1;
    for (int i = 1; i <= n; i++) {
        catalan[i] = catalan[i - 1] * (4 * i - 2) / (i + 1);
    }
    
    cout << catalan[n] << endl;
    return 0;
}
  1. 洛谷 P1976 鸡蛋饼
查看答案

思路：卡特兰数。

123456789101112131415161718192021222324252627282930313233#include <iostream>
using namespace std;

const int MOD = 1000000007;

int quickPowerMod(int a, int n, int mod) {
    int result = 1;
    a %= mod;
    while (n > 0) {
        if (n % 2 == 1) result = (long long)result * a % mod;
        a = (long long)a * a % mod;
        n /= 2;
    }
    return result;
}

int main() {
    int n;
    cin >> n;
    
    // C(2n, n) / (n+1)
    int numerator = 1, denominator = 1;
    for (int i = 0; i < n; i++) {
        numerator = (long long)numerator * (2 * n - i) % MOD;
        denominator = (long long)denominator * (i + 1) % MOD;
    }
    
    int result = (long long)numerator * quickPowerMod(denominator, MOD - 2, MOD) % MOD;
    result = (long long)result * quickPowerMod(n + 1, MOD - 2, MOD) % MOD;
    
    cout << result << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. Lucas 定理要求 p 是质数
  2. 卡特兰数有多种定义
  3. 组合计数要注意取模
  4. 进阶组合数学是难点