一.组合问题

$1$. 求组合数 $I$

递推:

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

数据范围：

$ 1≤n≤10000$
$ 1≤b≤a≤2000$

void init()
{
    for (int i = 0; i < N; 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]) % mod; // 关键等式
}

$2$. 求组合数 $II$

代入公式:

$$ {C_n^m} = {{n!} \over m!(n - m)!} $$

数据范围：

$1≤n≤10000$
$1≤b≤a≤10^5$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010, mod = 1e9 + 7;

int n;
int fact[N], infact[N];

int qmi(int a, int k) // 快速幂求逆元
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL) res * a % mod;
        a = (LL) a * a % mod;
        k >>= 1;
    }

    return res;
}

int main()
{
    fact[0] = infact[0] = 1; // 0的阶乘等于1,因此它的逆元也等于1
    for (int i = 1; i < N; i ++) 
    {
        fact[i] = (LL) fact[i - 1] * i % mod;
        infact[i] = (LL) infact[i - 1] * qmi(i, mod - 2) % mod; // mod是一个质数，所以运用小费马定理求出i的逆元
    }

    scanf ("%d", &n);

    while (n --)
    {
        int a, b;
        scanf ("%d %d", &a, &b);

        printf ("%d\n", (LL) fact[a] * infact[a - b] % mod * infact[b] % mod); // 三个数相乘可能爆long long，所以两个数相乘以后要及时取模
    }

    return 0;
}

$3$. 求组合数 $III$

卢卡斯定理:

$$ {C_n^m} ≡ {C_{n \% p}^{m \% p}} {C_{n \over p}^{m \over p}} (mod \quad p ) $$

数据范围：

$1≤n≤20$
$1≤b≤a≤10^{18}$
$1≤p≤10^5$(保证$p$为质数)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL) res * a % p;
        a = (LL) a * a % p;
        k >>= 1;
    }

    return res;
}

int C(int a, int b, int p)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j --) // i是[1 ~ b], j是[(a - b - 1) ~ a]
    {
        res = (LL) res * j % p;
        res = (LL) res * qmi(i, p - 2, p) % p; // 因为保证p是质数，所以可以用小费马定理求逆元
    }

    return res;
}

int lucas(LL a, LL b, int p) // Lucas定理(要递归实现)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL) C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; // a / p或b / p还可能大于p
}

int main()
{
    scanf ("%d", &n);

    while (n --)
    {
        int p;
        LL a, b;
        scanf ("%lld %lld %d", &a, &b, &p);
        printf ("%d\n", lucas(a, b, p));
    }

    return 0;
}

$4$. 求组合数 $IV$

求质因子的次数

数据范围:

$1≤b≤a≤5000$(求具体数字)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5010;

int primes[N], cnt;
int sum[N];
bool st[N];

void get_primes(int n) // 质数筛
{
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= n / i; j ++)
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get(int n, int x) // 求n!分解质因数后x的次数是多少
{
    int res = 0;
    while (n)
    {
        res += n / x;
        n /= x;
    }

    return res;
}

vector<int> mul(vector<int> a, int k) // 高精乘法,大数乘小数
{
    vector<int> res;

    int t = 0;
    for (int i = 0; i < a.size(); i ++)
    {
        t += a[i] * k;
        res.push_back(t % 10);
        t /= 10;
    }

    while (t) // t可能不止一位
    {
        res.push_back(t % 10);
        t /= 10;
    }

    return res;
}

int main()
{
    int a, b;
    scanf ("%d %d", &a, &b);

    get_primes(a);

    for (int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(b, p); // 分子的p的次数减去分母的p的次数
    }

    vector<int> res;
    res.push_back(1);

    for (int i = 0; i < cnt; i ++) // 质数的个数
        for (int j = 1; j <= sum[i]; j ++) // 质数的次方
            res = mul(res, primes[i]);

    for (int i = res.size() - 1; i >= 0; i --) printf ("%d", res[i]);
    return 0;
}

二. 卡特兰数

$$ H_n = C_{2n}^n - C_{2n}^{n-1}$$

$$ H_n = {C_{2n}^n \over n + 1} $$

$$ H_n = {4n - 2 \over n + 1 } H_{n - 1}$$

mod = 1e9 + 7;

int res = 1;
for (int i = n * 2; i > n; i --) res = (LL) res * i % mod; // [n + 1 ~ 2n]
for (int i = 1; i <= n; i ++) res = (LL) res * qmi(i, mod - 2, mod) % mod; // [1 ~ n]的逆元

res = (LL) res * qmi(n + 1, mod - 2, mod) % mod; // 1 / (n + 1) 的逆元