📖Mosquito's Note📖

组合数学

组合数

直接求解 组合数公式： Cnm=n!m!(n−m)!C_n^m = \frac{n!}{m!(n - m)!}

复杂度：

  • 时间：O(m)O(m)

特点：

  • 求单个组合数
#include <iostream>

using namespace std;
typedef long long ll;
ll res;

int n, m;

ll C(int a, int b)
{
    ll res = 1;
    for (int i = a, j = 1 ; j <= b ; i --, j ++)
        res = res * i / j; //会暴 long long

    return res;
}

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

    res = C(n, m);

    cout << res << endl;

    return 0;
}

高精度直接求解

由分解质因数部分可知，任何一个合数N都可以写成N=p1a1p2a2...pkakN = p_1^{a_1}p_2^{a_2}...p_k^{a_k}，即若干个质数的若干次幂的积

又由阶乘部分可知，阶乘中质因数的指数：cntpmi(a!)=⌊ap⌋+⌊ap2⌋+...+⌊apk⌋cnt_pmi(a!)= \left\lfloor\frac{a}{p}\right\rfloor + \left\lfloor\frac{a}{p^2}\right\rfloor + ... + \left\lfloor\frac{a}{p^k}\right\rfloor

那么只要先筛选出质数

然后分别求出各个质数的cntp(a!)mi,cntp(b!)mi,cntp((a−b)!)micnt_p(a!)mi, cnt_p(b!)mi, cnt_p(( a - b )!)mi

根据组合数公式： Cab=a!b!(a−b)!C_a^b = \frac{a!}{b!(a - b)!} 算出所有质数的指数，即k=cntpmi(a!)−cntpmi(b!)−cntpmi((a−b)!)k = cnt_pmi(a!) - cnt_pmi(b!) - cnt_pmi((a - b)!)

最后用大数乘小数的方式把结果算出来

#include <iostream>
#include <vector>

using namespace std;
const int N = 5010;
int primes[N], cnt;
int k[N];
bool st[N];

int a, b;

void get_primes(int x)
{
    for (int i = 2 ; i <= x ; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;

        for (int j = 0 ; primes[j] <= x / i ; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int get(int a, int p)
{
    int res = 0;

    while(a)
    {
        a /= p;
        res += a;
    }

    return res;
}

vector<int> mul(vector<int> &a, int p)
{
    vector<int> c;

    int t = 0;

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

    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }

    return c;
}

int main()
{
    cin >> a >> b;

    get_primes(a);//线性筛法

    for (int i = 0 ; i < cnt  ; i ++)
    {
        int p = primes[i];

        k[i] = get(a, p) - get(b, p) - get(a - b, p);//获取指数

    }

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

    for (int i = 0 ; i < cnt ; i ++)
        for (int j = 0 ; j < k[i] ; j ++)
            res = mul(res, primes[i]);//将质数的 k 次方全部乘起来

    for (int i = res.size() - 1 ; i >= 0  ; i --)
        cout << res[i] ;

    return 0;
}

递推求解

递推公式：Cnm=Cn−1m+Cn−1m−1C_n^m = C_{n-1}^m + C_{n-1}^{m-1}

证明可从两个角度：

  1. 杨辉三角某数等于其顶部左右两数之和
  2. 集合意义上从 n 个东西中选取 m 个的所有情况数等于
    • 第 n 个数不选取，从前 n - 1 中选 m 个数
    • 第 n 个数选取，从前 n - 1 中选取 m - 1 个数

复杂度：

  • 时间：O(n2)O(n^2)
  • 空间：O(n2)O(n^2)

特点：

  • 能简单求解多的组合数

在1≤n≤105,1≤b≤a≤20001 \leq n \leq 10^5, 1 \leq b \leq a \leq 2000的范围内可求解

#include <iostream>

using namespace std;
const int N = 2010, mod = 1e9 + 7;
int f[N][N];

int n;

int main()
{
    cin >> n;

    for (int i = 0 ; i < N ; i ++) f[i][0] = f[i][i] = 1;

    for (int i = 1 ; i < N ; i ++)
        for (int j = 1; j <= i / 2; j ++)
            f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] ) % mod,
            f[i][i - j] = f[i][j];

    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << f[a][b] << endl;
    }

    return 0;
}

预处理求解

使用公式求解Cnm=n!m!(n−m)!C_n^m = \frac {n! }{m!(n - m)! }
可以先预处理出 fact(n) , infact(m) , infact(n - m)，infact(x)表示 x!的逆元
则$C_n^m = fact(n) _ infact(m) _ infact( n - m ) $

一般题目 mod = 1e9 + 7 为质数，且 2~1e9+6 都与 1e9+7 互质，所以可以使用费马小定理、快速幂来求逆元，当然也可以使用扩展欧几里得来求。

复杂度：

  • 时间：O(nlogn)O(nlogn)

在1≤n≤104,1≤b≤a≤1051 \leq n \leq 10^4, 1 \leq b \leq a \leq 10^5的范围内可求解

#include <iostream>

using namespace std;
using LL = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];

int n;

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

int main()
{
    fact[0] = infact[0] = 1;

    for (int i = 1 ; i <= N ; i ++)
    {
        fact[i] = 1LL * fact[i - 1] * i % mod;
        infact[i] = 1LL * infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }

    cin >> n;

    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << (1LL * fact[a] * infact[b] % mod ) * infact[a - b] % mod << endl;//模两次是防止数据暴 long long
    }

    return 0;
}

优化

求阶乘的逆元使用费马小定理或扩展欧几里得的时间复杂度都为O(nlogn)O(nlogn)。事实上，可以先求出最后一个阶乘的逆元，再根据infact(n−1)=infact(n)∗ninfact(n - 1) = infact(n) * n线性递推出所有阶乘的逆元，使得预处理时间复杂度近似于O(n)O(n)

#include <iostream>

using namespace std;
using LL = long long;
const int N = 1e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];

int n;

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

int main()
{
    fact[0] = infact[0] = 1;

    for (int i = 1 ; i <= N ; i ++)
        fact[i] = 1LL * fact[i - 1] * i % mod;

    infact[N] = qmi(fact[N], mod - 2, mod);

    for (int i = N - 1 ; i >= 1; i --)
        infact[i] = 1LL * infact[i + 1] * (i + 1) % mod;

    cin >> n;

    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << (1LL * fact[a] * infact[b] % mod ) * infact[a - b] % mod << endl;
    }

    return 0;
}

卢卡斯定理求解

定理：Cab≡Ca%pb%p∗Ca/pb/p(mod p)C^b_a \equiv C_{a\%p}^{b\%p} * C_{a/p}^{b/p}(mod \space p)

证明：

复杂度：

  • 时间：O(logpN∗plogp)O(log_pN * plogp)

适用于 a，b 范围大样的情况求解，这题保证 p 为质数因此可以用费马小定理求逆元
在1 \leq n \leq 20，1 \leq b \leq a \leq 10^{18}，1 \leq p \leq 10^5的范围内可求解

其实是把 10^18 的 a, b 转换成小于 p 的数(10^5)求解，因此 a % p，b % p 小于 p，但是 a / p，b / p 有可能仍然大于 p，因此继续用 lucas 化小

#include <iostream>

using namespace std;
typedef long long LL;
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 = a, j = 1; j <= b ; j ++, i --)
        res = (LL)res * i % p,
        res = (LL)res * qmi(j, p - 2, p) % p;  //要乘上逆元，否则会出现除 j 为 0 的情况

    return res;

}

int lucas(LL a, LL b, int 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()
{
    cin >> n;
    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }

    return 0;
}

杨辉三角

性质：

  • 杨辉三角上任意一个数都可以用组合数表示
  • 杨辉三角上除了外围的数，任意一个数等于它上方左右两数之和
  • 杨辉三角是对称的，且半边杨辉三角的斜线有递增的性质，越靠近底，越靠近中间的的数越大
  • 杨辉三角正中间的数为C2kkC_{2k}^k
  • 杨辉三角上任意一个数的序号，可以由它的组合数得到，若该数为CabC_a^b，则该数的序号为(a + 1) * a + b + 1（从 1 开始）

二分求杨辉三角序号

#include <iostream>

using namespace std;
typedef long long LL;

int n;

LL C(int a, int b)
{
    LL res = 1;
    for (int i = a, j = 1 ; j <= b ; i -- , j ++)
    {
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
}

bool check(int k)
{
    LL l = k * 2, r = max(l, 1LL * n);

    while (l < r)
    {
        int mid = l + r >> 1;
        if (C(mid, k) >= n) r = mid;//同一条斜线上只有 C 的底数在变
        else l = mid + 1;
    }
    if (C(r, k) != n) return false;

    cout << r * (r + 1) / 2 + k + 1 << endl;

    return true;
}

int main()
{
    cin >> n;

    for (int i = 16 ; ; i --)
        if (check(i)) break;

    return 0;
}

排列数

单纯计算排列数的题目较少，计算的方法可以参考组合数

排列数公式：Aab=a!(a−b)!A_a^b = \frac{a!}{ ( a - b )! }

因为规定 0! = 1，则 A(0, 0) = 1

  1. 直接求解
  2. 高精度直接求解
  3. 预处理求解

错排公式

错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。n个元素的错排数记为DnD_n或!n!n。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题

递推求解

  • 递推公式： Dn=(n−1)(Dn−1+Dn−2)D_n = (n - 1)(D_{n - 1} + D_{n - 2} )
    表示将 n 个东西进行错排的方案数

    假设有 n 个数错排，先把第 n 个数放到第 k 个数的位置，k 的可取 n - 1 个(1≤k≤n−11 \leq k \leq n - 1)，这样完成第一个数的错位
    接着分为两种情况：

    1. 第 k 个数放在空出来的第 n 位置，这时还剩余 n - 2 个数进行错排，即Dn−2D_{n - 2}
    2. 第 k 个数不放在第 n 位置，此时相当第 n 个位置为 k 的原本位置，则包含 k 在内的 n - 1 个数进行错排，即Dn−1D_{n - 1}

    可得：Dn=(n−1)(Dn−1+Dn−2)D_n = (n - 1)(D_{n - 1} + D_{n - 2})

特别地，由公式的定义可知道D1=0,D2=1D_1=0, D_2 = 1

公式化简

推导及化简过程：点击跳转open in new window

公式：Dn=n!(12!−13!+...+(−1)n1n!)D_n = n!(\frac{1}{2!} - \frac{1}{3!} + ... + (-1)^n\frac{1}{n!})

化简：Dn=⌊n!e+0.5⌋D_n = \left\lfloor \frac{n!}{e} + 0.5 \right\rfloor

卡塔兰数

卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。历史上，清朝数学家明安图（1692 年－1763 年）在其《割圜密率捷法》中最先发明这种计数方式，远远早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。

卡塔兰数的一般项公式为：Cn=(2n)!(n+1)!n!C_n = \frac{(2n)!}{(n + 1)!n!}

递推关系公式：Cn+1=C0Cn+C1Cn−1+...+CnC0C_{n+1} = C_0C_n + C_1C_{n-1} + ... + C_nC_0

特别的 C0=1C_0 = 1

应用

组合数学中有非常多的组合结构可以用卡塔兰数来计数。以下用 n=3 和 n=4 举若干例：

  • CnC_n表示长度 2n 的dyck word的个数。Dyck 词是一个有 n 个 X 和 n 个 Y 组成的字串，且所有的前缀字符串皆满足 X 的个数大于等于 Y 的个数。以下为长度为 6 的 dyck

words：

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYYXXXYYY\space XYXXYY\space XYXYXY\space XXYYXY\space XXYXYY

  • 将上例的 X 换成左括号，Y 换成右括号，CnC_n表示所有包含 n 组括号的合法运算式的个数：

((())) ()(()) ()()() (())() (()())((()))\space ()(())\space ()()()\space (())()\space (()())

  • CnC_n表示有n个节点组成不同二叉数的方案数。

组合记数

组合计数理论是组合数学中一个最基本的研究方向，主要研究满足一定条件的安排方式的数目及其计数问题。本课程主要介绍组合数学中常见的和重要的一些计数原理、计数方法和计数公式，包括一般的排列、组合的计算以及生成函数、容斥原理、反演原理、Polya 计数定理等等，是研究组合数学的初步。

递推

递推关系（英语：Recurrence relation），在数学上也就是差分方程（Difference equation），是一种递推地定义一个序列的方程：序列的每一项目是定义为前若干项的函数。

像斐波那契数即为递推关系

xn+2=xn+1+xnx_{n+2}=x_{n+1}+x_{n}

某些简单定义的递推关系式可能会表现出非常复杂的（混沌的）性质，他们属于数学中的非线性分析领域。

所谓解一个递推关系式，也就是求其解析解，即关于 n 的非递归函数。

常见的递推

  • 等差数列

    an+1=an+ka_{n+1}=a_n + k

  • 等比数列

    an+1=kana_{n+1}=ka_{n}

  • 阶乘

    n!=(n−1)!n! = (n-1)!
    特别的 0!=10! = 1

  • 倒数和

    设 x_k = x^k + x^{-k}，则
    > x1=x1x_1 = x_1
    > x2=(x1)2−2x_2 = ( x_1 )^2 - 2
    > x3=x1∗x2−x1x_3 = x_1 * x_2 - x_1
    > x4=(x2)2−2x_4 = ( x_2 )^2 - 2
    ……
    > x2k=(xk)2−2x_{2k} = (x_k)^2 - 2
    > x2k+1=xk∗xk+1−x1x_{2k+1} = x_k * x_{k+1} - x_1

  • 斐波那契数

    F0=0F_0 = 0
    > F1=1F_1 = 1
    > Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}

  • 解线性递推
  • 常系数线性齐次递推

鸽剿原理

鸽巢原理，又名狄利克雷抽屉原理、鸽笼原理。

其中一种简单的表述法为：

若有 n 个笼子和 n+1 只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少 2 只鸽子。

另一种为：

若有 n 个笼子和 kn+1 只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少 k+1 只鸽子。

集合论的表述如下：

若 A 是 n+1 元集，B 是 n 元集，则不存在从 A 到 B 的单射。 拉姆齐定理是此原理的推广。

推广

一种表达是这样的：如果要把 n 个对象分配到 m 个容器中，必有至少一个容器容纳至少⌈nm⌉\displaystyle \left\lceil { \frac {n}{m} }\right\rceil个对象。

鸽巢原理经常在计算机领域得到真正的应用。比如：哈希表的重复问题（冲突）是不可避免的，因为 Keys 的数目总是比 Indices 的数目多，不管是多么高明的算法都不可能解决这个问题。这个原理，还证明任何无损压缩算法，在把一些输入变小的同时，作为代价一定有其他的输入增大，否则对于长度为 L 的输入集合，该压缩算法总能将其映射到一个更小的长度小于 L 的输出集合，而这与鸽巢理论相悖。

容斥原理

在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

集合公式：∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣A∩C∣+∣A∩B∩C∣|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|

例题： 分母是 1001 的最简分数一共有多少个？
分析：这一题实际上就是找分子中不能与 1001 进行约分的数。由于 1001=7×11×13，所以就是找不能被 7，11，13 整除的数。

解答：

  1. 1001 / 7 = 143; 1001 / 11 = 91; 1001 / 13 = 77;
  2. 1001 / (7 * 11) = 13; 1001 / (7 * 13) = 11; 1001 / (11 * 13) = 7
  3. 1001 / (7 * 11 * 13) = 1

则能被 7，11，13 整除的数共有(143 + 91 + 77) - (13 + 11 + 7) + 1 = 281 个

不能被其整除的数共有 1001 - 281 = 721 个