组合数学#

对于隔板法，要是分隔符之间可以为空，则得把分隔符也视作为元素，比如9人进6个通道，根据顺序和人和通道不同，有 $A^9_9 \times C^5_{14}$

组合#

对于数组元素的组合，保证后续的元素不和已经前面组合过的组合即可遍历所有状态空间。从左往右选和不选进行dfs

1
class Solution {
2
public:
3
    vector<vector<int>> combine(int n, int k) {
4
        vector<vector<int>> ans;
5

6
        vector<int> unit;
7
        auto dfs = [&](auto&& dfs, int elem) {
8
            int limit = k - unit.size();
9
            if (limit == 0) {
10
                return;
11
            }
12

13
            unit.push_back(elem);
14

15
            if (limit == 1) {
16
                ans.push_back(unit);
17
            }
18

19
            for (int index = elem + 1; index <= n; ++index) {
20
                dfs(dfs, index);
21
            }
22

23
            unit.pop_back();
24
        };
25

26
        for (int i = 1; i <= n; ++i) {
27
            dfs(dfs, i);
28
        }
29

30
        return ans;
31
    }
32
};

负数组合#

n + k - 1 可看作虚虚指针的距离

C^k_{-n} = (-1)^k \cdot C^k_{n+k-1}

TODO

Lucas定理#

p为素数，其余为自然数

\begin{pmatrix} m \\ n \end{pmatrix} \space mod\space p = \begin{pmatrix} \lfloor \frac{m}{p} \rfloor \\ \lfloor \frac{n}{p} \rfloor \\ \end{pmatrix} \cdot \begin{pmatrix} m\space mod\space p\\ n\space mod\space p\\ \end{pmatrix} \space mod\space p

实现

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4
const mod N = 1e5;
5
const ll mod = 998244353;//其实没什么用，lucas只能用于小质数模数
6
ll fact[N], ifact[N];
7

8
ll qp(ll a, ll b, ll p) {
9
    ll res = 1;
10
    while (b) {
11
        if (b & 1) res = res * a % p;
12
        a = a * a % p;
13
        b >>= 1;
14
    }
15
    return res;
16
}
17

18
void init(int n) {
19
    fact[0] = 1;
20
    for (int i = 1; i <= n; ++i) fact[i] = i * fact[i - 1] % mod;
21
    for (int i = 0; i <= n; ++i) ifact[i] = qp(fact[i], mod - 2, mod);
22
}
23

24
ll c(ll n, ll k) {
25
    if (k > n) return 0;
26
    return fact[n] % mod * ifact[k] % mod * ifact[n - k] % mod;
27
}
28

29
ll lucas(ll n, ll k) {
30
    if (!k) return 1;
31
    return c(n % mod, k % mod) * lucas(n / mod, k / mod) % mod;
32
}

排列#

st标记环，列举剩下集合非用过的可能的取值进行dfs

TODO

矩阵快速幂#

将快速幂思想迁移到递推式

以斐波那契数列为例

\begin{bmatrix} F[k] \\ F[k-1] \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} ^{k-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} =A^{k-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} ,\quad k=1 \ldots n

使用矩阵快速幂的前提是所求值可化为上一列各元素的线性组合，需要是常数，以 $F[i]=(ai+b)\times q^i$ 为例有

\begin{bmatrix} F[k] \\ a^k \end{bmatrix} = \begin{bmatrix} q & q \\ 0 & q \end{bmatrix} ^{k-1} \begin{bmatrix} b\\ a \end{bmatrix} ,\quad k = 1\ldots n

1
using ll = long long;
2

3
vector<vector<ll>> mul(const vector<vector<ll>>& a, const vector<vector<ll>> b, ll mod) {
4
    int n = a.size(), mid = a[0].size(), m = b[0].size();
5

6
    vector<vector<ll>> res(n, vector<ll>(m, 0));
7

8
    for (int i = 0; i < n; ++i) {
9
        for (int j = 0; j < m; ++j) {
10
            for (int k = 0; k < mid; ++k) {
11
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
12
            }
13
        }
14
    }
15

16
    return res;
17
}
18

19
vector<vector<ll>> mmi(vector<vector<ll>> A, ll b, ll mod) {
20
    vector<vector<ll>> res = {{1 % mod, 0}, {0, 1 % mod}};
21
    while (b) {
22
        if (b & 1) res = mul(res, A, mod);
23
        A = mul(A, A, mod);
24
        b >>= 1;
25
    }
26
    return res;
27
}

对于特殊的前缀和，也可以用矩阵快速幂进行计算，以

F[n] = \sum_{i = 1}^{n}{(ai+b) \times q^i}

为例，相对于 $F[i]=(ai+b)\times q^i$ 需要多留一行给求和积累效果

\begin{bmatrix} F[k - 1] \\ f[k] \\ a^k \end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 \\ 0 & q & q \\ 0 & 0 & q \end{bmatrix} ^{k-1} \begin{bmatrix} 0\\ b \\ a \end{bmatrix} ,\quad k = 1\ldots n

总结来说，矩阵快速幂有以下几个值得注意的点

前缀和只有其本身和组成单位有关，权为1
等比数列只和其所在列有关，权为q
$iq^i$ 和其所在列和对应和等比数列有关，权都为q
等差数列可看作常数C的前缀和

可见，矩阵快速幂对若干个等差数列和等比数列的线性组合和前缀和都适用，其他并不适用

矩阵快速幂如果用二维vector或者struct自行实现会被卡常，需要转化为维护变换的几个值和ans的几个值，

这里上三角矩阵的幂仍然是上三角矩阵，故变换可等价为右上角的6个值的递归，由于对角线独立幂化，故最左上角的1为定值1

下三角矩阵和上三角矩阵性质相同，而反上下三角矩阵性质则大有不同

音乐

音乐

组合数学#

组合#

负数组合#

Lucas定理#

排列#

矩阵快速幂#

文章分享

评论区

音乐

目录

音乐

音乐

6-组合数学

组合数学#

组合#

负数组合#

Lucas定理#

排列#

矩阵快速幂#

文章分享

评论区

音乐

目录