跳转至

4、数学

4.1 初等数论

4.1.1 同余式

​ 同余式是指两个整数除以同一个数的余数相等，也就是说，如果 \(a\) 和 \(b\) 是两个整数，\(m\) 是一个正整数，当 \(a\) 除以 \(m\) 的余数等于 \(b\) 除以 \(m\) 的余数时，我们说 \(a\) 和 \(b\) 对模 \(m\) 同余，记作 \(a \equiv b (\mod m)\)。

例如，当 \(m=3\) 时，\(10 \equiv 1 (\mod 3)\)，因为 \(10\) 除以 \(3\) 的余数是 \(1\)，而 \(1\) 除以 \(3\) 的余数也是 \(1\)。

​ 同余式在数论中有很多应用，比如求逆元、快速幂算法等都会用到同余式的性质。

4.1.2 欧拉定理和欧拉函数

​ 欧拉定理和欧拉函数是数论中的两个重要概念。

​ 欧拉定理：对于任意正整数 \(a\) 和 \(n\)，若 \(a\) 和 \(n\) 互质，则 \(a^{\varphi(n)}\equiv1\pmod{n}\)，其中 \(\varphi(n)\) 表示 \(n\) 的欧拉函数。

​ 欧拉函数：对于任意正整数 \(n\)，欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\) 的正整数中与 \(n\) 互质的数的个数。

例如，对于 \(n=8\)，小于等于 \(8\) 且与 \(8\) 互质的数为 \(1,3,5,7\)，因此 \(\varphi(8)=4\)。

以下是求欧拉函数和使用欧拉定理求逆元的 C++ 代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 求欧拉函数
int euler(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

//求快速幂算法
int qmi(int a, int k, int mod) {
    int res = 1 % mod;
    while (k) {
        if (k & 1) res = (long long)res * a % mod;
        a = (long long)a * a % mod;
        k >>= 1;
    }
    return res;
}

// 使用欧拉定理求逆元（要求 mod 是质数）
int inv(int a, int mod) {
    return qmi(a, mod - 2, mod);
}

4.1.3 费马小定理

​ 费马小定理是指，若 \(p\) 为质数，\(a\) 是整数且 \(p\) 不整除 \(a\)，则 \(a^{p-1} \equiv 1 \pmod{p}\)。这可以表示为 \(a^p \equiv a \pmod{p}\)，其中 \(a\) 与 \(p\) 互质。

例如，取 \(p = 7\) 和 \(a = 3\)，则 \(3^6 \equiv 1 \pmod{7}\)，即 \(3^7 \equiv 3 \pmod{7}\)。

​ 费马小定理是许多数论问题的基础，包括求解逆元和判断质数等。

下面是使用费马小定理求解逆元的 C++ 代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

using namespace std;

// 求 a^k mod m
int fast_pow(int a, int k, int m) {
    int res = 1;
    while (k) {
        if (k & 1) res = (long long)res * a % m;
        a = (long long)a * a % m;
        k >>= 1;
    }
    return res;
}

// 求 a 在模数 m 意义下的逆元
// 如果 a 与 m 不互质，则无逆元，返回 -1
int inverse(int a, int m) {
    if (a == 0 || m <= 0) return -1;
    return fast_pow(a, m - 2, m);
}

int main() {
    int a, m;
    cin >> a >> m;
    int inv = inverse(a, m);
    if (inv == -1) {
        cout << "No inverse exists." << endl;
    } else {
        cout << "The inverse of " << a << " mod " << m << " is " << inv << endl;
    }
    return 0;
}

​ 在上面的代码中，fast_pow 函数是快速幂算法，可以在 \(O(\log k)\) 的时间内求出 \(a^k\) 模 \(m\) 的值。

​ inverse 函数接受两个参数 \(a\) 和 \(m\)，其中 \(a\) 是需要求逆元的数，\(m\) 是模数。如果 \(a\) 与 \(m\) 不互质，则无法求出逆元，此时返回 -1。如果 \(a\) 与 \(m\) 互质，则可以根据费马小定理得到 \(a^{m-1} \equiv 1 \pmod m\)，从而得到 \(a^{-1} \equiv a^{m-2} \pmod m\)，然后调用 fast_pow 函数求解即可。

​ 在主函数中，首先读入 \(a\) 和 \(m\)，然后调用 inverse 函数求出逆元。如果逆元不存在，则输出 "No inverse exists."，否则输出逆元的值。

4.1.4 威尔逊定理

​ 威尔逊定理（Wilson's theorem）是一个关于质数的定理，它可以用来判断一个数是否为质数，或者判断一个数在模意义下是否有逆元。威尔逊定理的表述如下：

若 \(p\) 是一个质数，则 \((p-1)! \equiv -1 \pmod{p}\)。

​ 因此，如果我们需要判断一个数 \(x\) 是否为质数，可以计算 \((x-1)!\) 在模 \(x\) 意义下的值，如果等于 \(x-1\)，则 \(x\) 是一个质数。如果我们需要在模 \(p\) 意义下求一个数 \(x\) 的逆元，可以根据威尔逊定理得到：

\[x^{-1} \equiv (x-1)! \pmod{p}\]

​ 但需要注意的是，威尔逊定理只适用于质数，对于合数是不成立的。

​ 下面是使用威尔逊定理判断一个数是否为质数的 C++ 代码实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;

// 计算 x 的阶乘 % p 的值
int factorial(int x, int p) {
    int result = 1;
    for (int i = 2; i <= x; i++) {
        result = (result * i) % p;
    }
    return result;
}

// 判断 n 是否为质数
bool isPrime(int n) {
    if (n < 2) {
        return false;
    } else if (n == 2) {
        return true;
    } else if (n % 2 == 0) {
        return false;
    } else {
        // 判断 n 是否满足威尔逊定理的条件
        int p = n;
        int f = factorial(p - 1, p);
        return (f == p - 1);
    }
}

int main() {
    int n;
    cout << "请输入一个整数：";
    cin >> n;
    if (isPrime(n)) {
        cout << n << " 是质数。" << endl;
    } else {
        cout << n << " 不是质数。" << endl;
    }
    return 0;
}

4.1.5 裴蜀定理

​ 裴蜀定理，也称为贝祖定理，是指对于任意给定的两个整数 \(a\) 和 \(b\)，它们的最大公约数 \(gcd(a,b)\)，必定可以表示成 \(ax+by\) 的形式，其中 \(x\) 和 \(y\) 为整数。这个定理的应用非常广泛，比如可以用来判断两个整数是否互质，以及求解一元线性不定方程等。

​ 以下是使用扩展欧几里得算法求解裴蜀定理的 C++ 代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
using namespace std;

// 扩展欧几里得算法
int extgcd(int a, int b, int &x, int &y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= a / b * x;
    }
    else {
        x = 1;
        y = 0;
    }
    return d;
}

// 求裴蜀定理
bool bezout(int a, int b, int c, int &x, int &y) {
    int x0, y0;
    int d = extgcd(a, b, x0, y0);
    if (c % d != 0) return false;
    x = x0 * c / d;
    y = y0 * c / d;
    return true;
}

int main() {
    int a, b, c;
    cout << "Enter a, b and c: ";
    cin >> a >> b >> c;
    int x, y;
    bool solvable = bezout(a, b, c, x, y);
    if (solvable) {
        cout << "The equation " << a << "x + " << b << "y = " << c << " has a solution: x = " << x << ", y = " << y << endl;
    }
    else {
        cout << "The equation " << a << "x + " << b << "y = " << c << " has no solution." << endl;
    }
    return 0;
}

使用示例：

输入：

C++
1
Enter a, b and c: 16 10 6

输出：

C++
1
The equation 16x + 10y = 6 has a solution: x = -1, y = 2

4.1.6 逆元

​ 逆元是指对于模数m，如果a和m互质，那么存在一个整数b，使得ab ≡ 1(mod m)，b就是a的逆元，通常用a^{-1}表示。

​ 在数学中，求a的逆元的方法有欧几里得扩展算法和费马小定理求逆元两种常见方法。

1.欧几里得扩展算法

​ 欧几里得扩展算法又称扩展欧几里得算法，可以在O(log n)的时间内求出任意一组整数a、b的最大公约数gcd(a, b)，并找到整数x、y，使它们满足贝祖等式ax + by = gcd(a, b)。

​ 根据贝祖等式，我们可以通过不断的变形得到逆元的求解公式：

ax + my = 1，其中m为模数，因为ax ≡ 1 (mod m)，所以x就是a在模m意义下的逆元。

2.费马小定理求逆元

​ 费马小定理指出，对于任何一个质数p，对于整数a（a不是p的倍数），有a^{p-1} \equiv 1 \pmod{p}，因此a的逆元就是a^{p-2}。当p不是质数时，这个结论不再成立，但是可以通过扩展欧几里得算法来求解逆元。

下面给出使用扩展欧几里得算法求逆元的C++代码实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 扩展欧几里得算法求逆元
// 返回值x是a在模m下的逆元，若不存在返回-1
int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int mod_inv(int a, int m) {
    int x, y;
    int d = exgcd(a, m, x, y);
    if (d != 1) return -1;
    return (x % m + m) % m;
}

​ 上述代码实现了使用扩展欧几里得算法来求解a在模m下的逆元。其中exgcd函数是扩展欧几里得算法的具体实现，mod_inv函数是求逆元的接口函数，它在使用exgcd函数求得x和y后，判断是否存在逆元，若存在则返回x在模m下的结果，否则返回-1。

​ 需要注意的是，如果在模m下不存在a的逆元，那么会返回-1。在使用逆元时，需要对该返回值进行判断。

4.1.7 扩展欧几里得算法

​ 扩展欧几里得算法是求解线性同余方程 ax ≡ b (mod m) 的一种方法，其中 a、b 和 m 都是整数，且 a 和 m 互质。该算法除了求解方程的解 x 外，还能够求解方程 ax + my = b 的一组整数解 x 和 y。其基本思想是通过递归调用的方式，利用欧几里得算法求解出最大公约数，并沿途记录下一些系数，最终得到方程的一个特解和通解。

以下是扩展欧几里得算法的 C++ 代码实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>

using namespace std;

// 返回最大公约数和贝祖等式x, y的解
// ax + by = gcd(a, b)
int extended_euclidean(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int gcd = extended_euclidean(b, a % b, x, y);
    int tmp = x;
    x = y;
    y = tmp - a / b * y;
    return gcd;
}

int main() {
    int a = 10, b = 6;
    int x, y;
    int gcd = extended_euclidean(a, b, x, y);
    cout << "gcd(" << a << ", " << b << ") = " << gcd << endl;
    cout << a << " * " << x << " + " << b << " * " << y << " = " << gcd << endl;
    return 0;
}

运行结果：

C++
1
2
gcd(10, 6) = 2
10 * -1 + 6 * 2 = 2

​ 以上代码中，extended_euclidean 函数的输入为两个整数 a 和 b，输出为最大公约数 gcd 和贝祖等式 ax + by = gcd(a, b) 的解 x 和 y。函数的返回值为最大公约数 gcd。

4.1.8 孙子定理（即中国剩余定理）

​ 孙子定理，又称中国剩余定理，是解决同余方程组问题的一种方法。它适用于一般形式的同余方程组，方程的系数不必是互质的。

​ 假设有 \(n\) 个方程，其同余条件为：$$ x\equiv a_1\pmod {m_1}, x\equiv a_2\pmod {m_2}, \cdots, x\equiv a_n\pmod {m_n} $$ 其中 \(a_1,a_2,\cdots,a_n\) 和 \(m_1,m_2,\cdots,m_n\) 两两互不相同，我们需要求出 \(x\) 的值。根据孙子定理，这个问题等价于：$$ x\equiv r_1\pmod {M_1}, x\equiv r_2\pmod {M_2}, \cdots, x\equiv r_n\pmod {M_n} $$ 其中 \(r_i\) 和 \(M_i\) 的定义如下：$$ M=\prod_{i=1}^{n}m_i, M_i=\frac{M}{m_i}, r_i\equiv M_i^{-1}\pmod {m_i} $$ 其中 \(M_i^{-1}\) 表示 \(M_i\) 在模 \(m_i\) 意义下的逆元。然后根据同余方程组的性质，\(x\) 可以表示为：$$ x=\sum_{i=1}^{n}r_iM_ix $$ 我们只需要求出 \(M_i\) 的逆元和 \(r_i\)，就可以根据上述式子求出 \(x\) 的值。

以下是使用 C++ 实现孙子定理的代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
using namespace std;

// 求a^b mod m的值
long long pow_mod(long long a, long long b, long long m) {
    long long ans = 1 % m;
    while (b) {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

// 扩展欧几里得算法
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 求孙子定理的解，x ≡ a1 (mod m1)，x ≡ a2 (mod m2)
long long sunzi(long long a1, long long m1, long long a2, long long m2) {
    long long x, y;
    long long d = exgcd(m1, m2, x, y);
    if ((a1 - a2) % d != 0) return -1;
    long long m = m1 / d * m2;
    x = ((a2 - a1) % m2 * x % m + m) % m;
    return x;
}

int main() {
    vector<long long> a = {2, 3, 2}; // 余数
    vector<long long> m = {3, 5, 7}; // 模数
    long long x = a[0], M = m[0];
    for (int i = 1; i < a.size(); i++) {
        x = sunzi(x, M, a[i], m[i]);
        if (x == -1) {
            cout << "No solution." << endl;
            return 0;
        }
        M *= m[i] / exgcd(M, m[i], M, M);
    }
    cout << "The solution is: " << x << endl;
    return 0;
}

​ 以上代码实现了孙子定理，求解形如 x ≡ a1 (mod m1)，x ≡ a2 (mod m2)，...，x ≡ an (mod mn) 的同余方程组。其中 a 是余数，m 是模数，x 是方程的解。sunzi 函数求解两个同余方程的解，使用扩展欧几里得算法求解逆元。最后，遍历所有的同余方程，使用 x 和 M 分别记录当前的解和模数，然后更新 x 和 M，得到所有同余方程的解。如果无解，则返回 -1。

4.2 组合数学

4.2.1 可重集排列

​ 可重集排列指的是将一个由\(n\)个元素组成的可重集合理解为一个长度为\(n\)的序列，并对该序列进行全排列。假设该可重集合中元素\(a_i\)出现的次数为\(c_i\)，则该可重集合的不同排列数为：

\[\frac{(c_1+c_2+\cdots+c_n)!}{c_1!c_2!\cdots c_n!}\]

​ 其中\(c_1+c_2+\cdots+c_n\)为该可重集合的元素总数。

​ 可以使用回溯算法解决可重集排列问题。遍历所有的排列，对于每个位置，枚举该位置可以填入哪些元素，然后进入下一层递归。当排列长度达到\(n\)时，即可将该排列加入结果集中。需要注意的是，对于每个位置，不能选择该元素的数量超过\(c_i\)个。在实现时，可以使用一个哈希表记录每个元素的数量，每次选择元素后将该元素的数量减1，递归完成后再将该元素的数量加1，恢复现场。

以下是使用 C++ 实现可重集排列的代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 计算阶乘
int fact(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

// 计算重复因子的积
int repeat_factorial(const vector<int>& freq) {
    int result = 1;
    for (int i = 0; i < freq.size(); i++) {
        if (freq[i] > 1) {
            result *= fact(freq[i]);
        }
    }
    return result;
}

// 计算可重集合排列的数量
int permutation(const vector<int>& freq) {
    int n = 0;
    for (int i = 0; i < freq.size(); i++) {
        n += freq[i];
    }
    int result = fact(n) / repeat_factorial(freq);
    return result;
}

// 生成可重集合的全排列
void generate_permutation(vector<int>& freq, vector<int>& permutation, vector<vector<int>>& result) {
    int n = 0;
    for (int i = 0; i < freq.size(); i++) {
        n += freq[i];
    }
    if (n == permutation.size()) {
        result.push_back(permutation);
        return;
    }
    for (int i = 0; i < freq.size(); i++) {
        if (freq[i] > 0) {
            freq[i]--;
            permutation.push_back(i);
            generate_permutation(freq, permutation, result);
            permutation.pop_back();
            freq[i]++;
        }
    }
}

int main() {
    vector<int> freq = {2, 1, 1};
    int n = permutation(freq);
    cout << "可重集合的全排列数量为：" << n << endl;

    vector<vector<int>> result;
    vector<int> permutation;
    generate_permutation(freq, permutation, result);
    cout << "可重集合的全排列为：" << endl;
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

​ 在这个代码中，我们首先定义了两个函数 fact 和 repeat_factorial 分别用于计算阶乘和重复因子的积。其中，fact 函数用于计算阶乘，repeat_factorial 函数用于计算可重集合的重复因子的积。接下来，我们定义了函数 permutation 用于计算可重集合的全排列数量，并使用函数 generate_permutation 生成可重集合的全排列。最后，我们在主函数中测试了代码的正确性。

4.2.2 可重集组合

​ 可重集组合问题指从一个包含 n 种元素的可重集合中选出 k 个元素，使得元素的顺序不考虑，且每个元素可以重复选取多次的方案数。这个问题可以使用类似于背包问题的动态规划思路来解决。

​ 具体来说，设 dp[i][j] 表示从前 i 个元素中选取 j 个元素的可重集合的方案数，其中第 i 个元素可以选取多次。则有以下状态转移方程：

dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]

​ 其中 dp[i-1] [j] 表示不选第 i 个元素，dp[i] [j-1] 表示至少选一次第 i 个元素。需要注意的是，在 dp[i] [j-1] 中，因为第 i 个元素可以选取多次，所以实际上是选取的是前 i 个元素中选取 j-1 个元素的可重集合，再加上选取了第 i 个元素。因此，dp[i] [j-1] 应该被拆分成 dp[i-1] [j-1] + dp[i] [j-2]，其中 dp[i-1] [j-1] 表示选取了一次第 i 个元素，dp[i] [j-2] 表示选取了至少两次第 i 个元素。

​ 最终，可重集合的方案数为 dp[n] [k]。

以下是使用动态规划实现可重集组合问题的 C++ 代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1000; // 可重集合的最大元素个数
const int MAXM = 1000; // 容量限制

int n;          // 可重集合中元素的个数
int m;          // 容量限制
int w[MAXN+1];  // 可重集合中每个元素的重量
int c[MAXN+1];  // 可重集合中每个元素的价值
int f[MAXM+1];  // f[i]表示容量为i时的最大价值

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> w[i];
    for(int i = 1; i <= n; i++)
        cin >> c[i];

    memset(f, 0, sizeof(f));

    for(int i = 1; i <= n; i++) {
        for(int j = w[i]; j <= m; j++) {
            f[j] = max(f[j], f[j-w[i]]+c[i]);
        }
    }

    cout << f[m] << endl;

    return 0;
}

​ 其中，w[i]表示第i个元素的重量，c[i]表示第i个元素的价值，f[i]表示容量为i时的最大价值。在循环中，我们对于每一个元素，从其自身重量开始向容量m遍历，更新每一个容量下的最大价值。最终，f[m]即为所求的可重集合组合问题的答案。

4.2.3 错排列、圆排列

​ 错排列（Derangement）和圆排列（Circular Permutation）是排列问题中的两个经典问题。

​ 错排问题是指在有n个元素的排列中，元素不在其原有的位置上的排列总数，即排列中每个位置的元素都与原序列中对应位置的元素不同。错排问题也叫重排列问题。

​ 圆排列问题是指在有n个元素的排列中，任意一个位置都可以作为排列的开头，而这些不同的排列被认为是等价的。

​ 下面分别介绍它们的计算方法。

错排列

​ 错排问题可以使用递推或数学公式求解。下面分别介绍两种方法。

1.递推方法

设\(f(n)\)为有n个元素的错排数，则：

​ 当\(n=0\)时，\(f(0)=1\)； 当\(n=1\)时，\(f(1)=0\)； 当\(n=2\)时，\(f(2)=1\)； 当\(n>2\)时，第一个元素有\(n-1\)种不同的放置方法，放置第一个元素后，问题就变成了有\(n-1\)个元素的错排问题。此时，放置第一个元素后剩余的\(n-1\)个元素不能放在其对应的位置上，共有\(f(n-1)\)种不同的错排方法。因此，有如下递推关系式：

\[f(n)=(n-1) \times (f(n-1)+f(n-2))\]

2.数学公式方法

​ 根据排列组合知识，有\(n\)个元素的全排列共有\(n!\)种，而错排问题实际上就是求\(n\)个元素的全排列中，元素恰好不在其原来位置上的排列数。设有\(D(n)\)种这样的排列，则：

\[D(n)=n!- \sum_{i=1}^{n} \frac{n!}{i!}\]

​ 上式中，第\(i\)项是指\(n\)个元素中恰好有\(i\)个元素不在其原来位置上的排列数。

圆排列

​ 圆排列指的是将 \(n\) 个不同的物品排成一个环，且不考虑环的方向。与排列问题类似，圆排列的总数可以用容斥原理求得。

​ 对于 \(n\) 个物品的圆排列问题，总的排列数为 \((n-1)!\)。然而，由于这些排列是围成一个圆形的，所以我们需要除以 \(n\)，以消除圆排列的等价性。也就是说，若存在 \(k\) 个排列在圆上重合，那么这些排列都是等价的，即只算一个排列。因此，总数为 \(\frac{(n-1)!}{n} = (n-2)!\)。

​ 若我们要计算 \(n\) 个物品的圆排列中，至少有 \(m\) 个物品固定不动的排列数，我们可以先选定 \(m\) 个物品，它们必须排在固定位置上。这些物品固定不动，因此只需要在 \(n-m\) 个剩余物品中选出 \((n-m-1)!\) 个排列即可，最后再将 \(m\) 个物品插入到 \((n-m-1)!\) 个排列的不同位置上。因此，\(n\) 个物品的圆排列中，至少有 \(m\) 个物品固定不动的排列数为 \((n-m-1)!m\)。

​ 下面是圆排列的 C++ 代码实现，其中使用了阶乘预处理的方法，可以提高计算效率：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

// 计算 n 的阶乘
int factorial(int n) {
    int res = 1;
    for (int i = 2; i <= n; ++i) {
        res *= i;
    }
    return res;
}

// 计算圆排列的数量
int circular_permutation(int n) {
    return factorial(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << circular_permutation(n) << endl;
    return 0;
}

​ 代码中，factorial 函数计算 \(n\) 的阶乘，circular_permutation 函数计算圆排列的数量，即 \((n-1)!\)。最后读入 \(n\)，输出圆排列的数量。

4.2.4 鸽巢原理

​ 鸽巢原理，也称为抽屉原理，是数学中的一种基本定理。它表明，如果将多于 \(n\) 个物体放入 \(n\) 个鸽巢中，则必定有一个鸽巢中至少放了两个物体。鸽巢原理可以用于求解各种组合问题，是许多算法的基础。

​ 举个例子，假设有 \(n+1\) 个人要参加一个大小为 \(n\) 的会议，每个人要么参加要么不参加。那么根据鸽巢原理，至少有两个人要么都参加，要么都不参加，因为有 \(n+1\) 个人，而只有两个选择，参加或不参加。

在编程竞赛中，鸽巢原理常用于解决如下问题：

  • 求多个数中出现次数大于 \(\frac{n}{k}\) 的数。
  • 求多个数中最大和最小值的最小距离。
  • 求一个字符串中是否有长度为 \(k+1\) 的子串出现至少 \(k\) 次。

​ 在实际应用中，鸽巢原理也可以推广到更高维度的情况，例如将 \(n\) 个球放入 \(m\) 个箱子中，每个球的颜色不同，每个箱子的容量相等，每个箱子内球的颜色不同，要求每个球都恰好放在一个箱子中。那么由于共有 \(nm\) 个位置，而有 \(n\) 个球，因此至少有一个箱子中有两个及以上的球。

​ 以下是一个简单的求解鸽巢原理的 C++ 代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m; // n 个鸽子，m 个鸟巢
    if (n > m) {
        cout << "Pigeons cannot be put into bird nests." << endl;
    } else {
        int num = m / n;
        int remain = m % n;
        if (remain > 0) num++;
        cout << "At least " << num << " bird nests contain at least one pigeon." << endl;
    }
    return 0;
}

​ 该程序先输入了 n 个鸽子和 m 个鸟巢的数量，然后判断了鸽子的数量是否大于鸟巢的数量，若是，则无法将鸽子全部放入鸟巢中，程序输出一条错误信息；若否，则计算每个鸟巢中至少应该放几只鸽子，最后输出结果。注意，程序中使用了整数除法和取模运算来计算每个鸟巢中至少应该放几只鸽子。

4.2.5 二项式定理

​ 二项式定理是一个关于 \((a+b)^n\) 的公式，其中 \(a,b\) 为实数，\(n\) 为正整数。它可以写成如下形式：

\[(a+b)^n = \sum_{i=0}^n \binom{n}{i}a^{n-i}b^i\]

​ 其中，\(\binom{n}{i}\) 表示从 \(n\) 个不同的元素中，取出 \(i\) 个元素的组合数，也称为二项式系数，可以用下面的公式计算：

\[\binom{n}{i}=\frac{n!}{i!(n-i)!}\]

​ 二项式定理在组合数学、高中数学和大学数学中都有广泛的应用。

4.2.6 容斥原理

Text Only
1
容斥原理是组合数学中常用的计数技巧，用于求解多重集合的交集、并集等问题。该原理的核心思想是：对于多个集合的交集或并集，可以先求出每个集合的元素个数，再根据容斥原理计算它们的交集或并集的元素个数。

​ 在组合数学中，容斥原理可以表述为：如果A1，A2，…，An是任意n个集合，则这些集合的并集的大小可以通过以下公式来计算：

|A1 ∪ A2 ∪ ... ∪ An| = Σ|Ai| - Σ|Ai ∩ Aj| + Σ|Ai ∩ Aj ∩ Ak| - ... +(-1)^(n-1)|A1 ∩ A2 ∩ ... ∩ An|

​ 其中，Σ表示求和，|A|表示集合A的元素个数，∪表示集合的并集，∩表示集合的交集，(-1)^(n-1)表示(-1)的(n-1)次幂。

​ 该公式的意义是，首先将所有集合的元素数量相加，得到这些集合的总元素数，然后依次减去它们的交集、并集、三者交集……直到最后的并集。

​ 容斥原理常常被用于解决各种计数问题，如排列组合问题、随机事件计算等等。

下面是一个使用容斥原理计算两个集合交集大小的简单示例的 C++ 代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> A = {1, 3, 5, 7, 9};
    set<int> B = {2, 3, 5, 7, 11};
    set<int> C;
    for (int x : A) {
        if (B.count(x)) {
            C.insert(x);
        }
    }
    int n = A.size() + B.size() - C.size();
    cout << "A ∩ B 的大小为 " << C.size() << endl;
    cout << "A ∪ B 的大小为 " << n << endl;
    return 0;
}

输出：

Text Only
1
2
A ∩ B 的大小为 3
A ∪ B 的大小为 7

4.2.7卡特兰数

​ 卡特兰数是一类组合数学中的数列，其通项公式为： \(\(C_n=\frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{(n+1)!n!}\)\) 卡特兰数在计数问题中有着广泛的应用，比如括号匹配问题、山峰与山谷问题、进出栈序列问题等。

以下是卡特兰数的一些性质：

  • \(C_0=1\)
  • \(C_n\) 的值增长速度非常快，近似于 \(4^n\)
  • \(C_n\) 是整数，并且对于任意 \(n>0\)，\(C_n\) 都是偶数
  • \(C_n\) 是 \((n+1)\) 阶 Bell 数列的第 \(n\) 项

以下是卡特兰数的 C++ 动态规划代码实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>

using namespace std;

// 计算卡特兰数
long long catalan(int n) {
    if (n == 0) {
        return 1;
    }
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    return dp[n];
}

int main() {
    int n = 10;
    long long ans = catalan(n);
    cout << "The " << n << "th catalan number is " << ans << endl;
    return 0;
}
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用