组合数学笔记

First Post:
Last Update:

组合数应用甚为广泛，之前做过笔记，这次算补档。

组合数学的先行版

我记得我记过组合数学的笔记呀😡

求组合数

求组合数有很多种方式，我们需要通过数据范围来选出适合的方式，以如下例题为例👇

  • 给定 n 组询问，每组询问给定两个整数 a，b请你输出 C a b mod(10^9+7) 的值。

第一种（递推式）

公式： C(a, b) = C (a - 1, b) + C(a - 1, b - 1)

此类方法的数据范围： 10 ^ 3 < b ≤ a < 10 ^ 4

代码实现：

#include <iostream>

using namespace std;

const int N = 2010;
const int MOD = 1e9 + 7;

int c[N][N];

void init()                         //时间复杂度O(n ^ 2), 空间复杂度O(n ^ 2)
{
    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 - 1] + c[i - 1][j]) % MOD;       //递推    
        }
    }
}

int main()
{
    init();

    int T;
    cin >> T;

    while(T -- )
    {
        int a, b;
        cin >> a >> b;

        cout << c[a][b] << endl;
    }

    return 0;
}

第二种（乘法逆元和前缀乘预处理）

公式： C(a, b) = a! / [(a - b)! × b!] ==> C(a, b) = a! × inv((a- b)! × b!)

此类方法的数据范围： 1 ≤ b ≤a ≤ 10^5

代码实现：

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

int fact[N], inv[N];

int qkm(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;
}

void init()
{
    fact[0] = inv[0] = 1;           //c(0,0)的初始化
    for(int i = 1; i < N; i ++ )
    {
        fact[i] = (LL)fact[i - 1] * i % MOD;        // 前缀乘or阶乘递推
        inv[i] = (LL) inv[i - 1] * qkm(i, MOD - 2, MOD) % MOD;
    }
}

int main()
{
    int T;
    cin >> T;

    init();

    while(T -- )
    {
        int a, b;
        cin >> a >> b;

        cout << ((LL)fact[a] * inv[b] % MOD * inv[a- b] % MOD) % MOD << endl;
    }

    return 0;
}

第三种（Lucas定理）

公式： C(a, b) % P = C(a%P, b%P) × C(a/P, b/P)

此类方法的数据范围： 1≤b≤a≤10^18, 1≤p≤10^5

代码实现：

#include <iostream>

using namespace std;

typedef long long LL;

int qkm(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = 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 -- )
    {
        res = (LL)res * j % p;              //阶乘的递推
        res = (LL)res * qkm(i, p - 2, p) % p;       	//乘法逆元
    }

    return res;
}

int lucas(LL a, LL b, int p)        //lucas定理中p为质数,且不宜太大
{
    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;
}

int main()
{
    int T;
    cin >> T;

    while(T -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

第四种(对阶乘分解质因数 + 高精度)

及其硬核，不是吗

当以上范围超出以上三种或没有进行取余

代码实现：

#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[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}


int get(int n, int p)
{
    int res = 0;
    while (n)
    {
        res += n / p;
        n /= p;
    }
    return res;
}


vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}


int main()
{
    int a, b;
    cin >> 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);
    }

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

    for (int i = 0; i < cnt; i ++ )
        for (int j = 0; j < sum[i]; j ++ )
            res = mul(res, primes[i]);

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

    return 0;
}

下次拿python覆写一遍。

番外の数——卡特兰数

作为卡特兰数，这个世界上很多方案数都是卡特兰数，拥有和斐波那契数一样的地位

表达形式：

  1. f(n)=f(0)×f(n−1)+f(1)×f(n−2)+…+f(n−1)×f(0)
  2. f(n)=C(2n, n) - C(2n , n - 1)
  3. f(n)=C(2n, n) / (n + 1)

卡特兰数的初始化： f(0) = 1

例题展示

给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。

输出的答案对 10^9+7 取模。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示答案。

数据范围

1≤n≤10^5

输入样例：

3

输出样例：

5

代码实现：

#include <iostream>

using namespace std;

typedef long long LL;

const int MOD = 1e9 + 7;

int qkm(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 main()
{
    int n;
    cin >> n;

    int a = n * 2;
    int b = n;

    int f = 1;

    for(int i = a; i > b; i -- ) f = (LL)f * i % MOD;

    for(int i = 1; i <= n; i ++ ) f = (LL)f * qkm(i, MOD - 2, MOD) % MOD;

    cout << f << endl;

    return 0;
}

暂完