求组合数

递推法

原理

见《进阶指南》第170页。

模板题

AcWing-885-求组合数 I

#include <iostream>
using namespace std;

const int N = 2010, M = 1e9 + 7;
int C[N][N];

void initialize () {
    for (int i = 0; i < N; ++ i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++ j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
    }
}

int main () {
    initialize();
    int T;
    cin >> T;
    while (T --) {
        int n, m;
        cin >> n >> m;
        cout << C[n][m] << endl;
    }
    return 0;
}

预处理阶乘的乘法逆元

原理

见《进阶指南》第170页。

模板题

AcWing-886-求组合数 II

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 100010, M = 1e9 + 7;
int f[N], inv_f[N];

int power (int a, int b, int p) {
    int res = 1 % p;
    while (b > 0) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b /= 2;
    }
    return res;
}
void initialize () {
    f[0] = inv_f[0] = 1;
    for (int i = 1; i < N; ++ i) {
        f[i] = (LL)i * f[i - 1] % M;
        inv_f[i] = (LL)power(i, M - 2, M) * inv_f[i - 1] % M;
    }
}
int C (int n, int m) {
    return (LL)f[n] * inv_f[m] % M * inv_f[n - m] % M; // 乘一次模一次
}

int main () {
    initialize();
    int T;
    cin >> T;
    while (T --) {
        int n, m;
        cin >> n >> m;
        cout << C(n, m) << endl;
    }
    return 0;
}

Lucas定理

原理

见《进阶指南》第173页。

模板题

AcWing-887-求组合数 III

#include <iostream>
using namespace std;

typedef long long LL;

int power (int a, int b, int p) {
    int res = 1 % p;
    while (b > 0) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b /= 2;
    }
    return res;
}
int C (int n, int m, int p) {
    int a = 1, b = 1;
    for (int i = 1, j = n; i <= m; ++ i, -- j) {
        a = (LL)a * j % p;
        b = (LL)b * i % p;
    }
    return (LL)a * power(b, p - 2, p) % p;
}
int Lucas (LL n, LL m, int p) {
    if (n < p && m < p)
        return C(n, m, p);
    return (LL)C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

int main () {
    int T;
    cin >> T;
    while (T --) {
        LL n, m;
        int p;
        cin >> n >> m >> p;
        cout << Lucas(n, m, p) << endl;
    }
    return 0;
}

高精度

原理

见《进阶指南》第170页。

模板题

AcWing-888-求组合数 IV

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 5010;
int idx, primes[N];
bool mark[N];
int e[N];

void get_primes (int n) {
    for (int i = 2; i <= n; ++ i) {
        if (mark[i] == false) primes[++ idx] = i;
        for (int j = 1; primes[j] <= n / i; ++ j) {
            mark[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}
int get_e (int n, int p) { // 求 n! 的质因数 p 的幂次
    int res = 0;
    while (n > 0) {
        res += n / p;
        n /= p;
    }
    return res;
}
vector<int> mul (vector<int>& A, int b) {
    vector<int> C;
    int carry = 0;
    for (int i = 0; i < A.size() || carry != 0; ++ i) {
        if (i < A.size()) carry += A[i] * b;
        C.push_back(carry % 10);
        carry /= 10;
    }
    return C;
}

int main () {
    int n, m;
    cin >> n >> m;

    get_primes(n);
    for (int i = 1; i <= idx; ++ i) {
        int p = primes[i];
        e[i] = get_e(n, p) - get_e(m, p) - get_e(n - m, p);
    }
    vector<int> res(1, 1);
    for (int i = 1; i <= idx; ++ i)
        for (int j = 1; j <= e[i]; ++ j)
            res = mul(res, primes[i]);
    
    reverse(res.begin(), res.end());
    for (int d: res) cout << d;
    return 0;
}