2 组合数学

2.1 组合数学常见性质

\(k *C^k_n=n*C^{k-1}_{n-1}\) ；
\(C_k^n*C_m^k=C_m^n*C_{m-n}^{m-k}\) ；
\(C_n^k+C_n^{k+1}=C_{n+1}^{k+1}\) ；
\(\sum_{i=0}^n C_n^i=2^n\) ；
\(\sum_{k=0}^n(-1)^k*C_n^k=0\) 。
二项式反演：\(\left\{\begin{matrix} \displaystyle f_n=\sum_{i=0}^n{n\choose i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}f_i \\ \displaystyle f_k=\sum_{i=k}^n{i\choose k}g_i\Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}{i\choose k}f_i \end{matrix}\right.\) ；
\(\displaystyle \sum_{i=1}^{n}i{n\choose i}=n * 2^{n-1}\) ；
\(\displaystyle \sum_{i=1}^{n}i^2{n\choose i}=n*(n+1)*2^{n-2}\) ；
\(\displaystyle \sum_{i=1}^{n}\dfrac{1}{i}{n\choose i}=\sum_{i=1}^{n}\dfrac{1}{i}\) ；
\(\displaystyle \sum_{i=0}^{n}{n\choose i}^2={2n\choose n}\) ；
拉格朗日恒等式：\(\displaystyle \sum_{i=1}^{n}\sum_{j=i+1}^{n}(a_ib_j-a_jb_i)^2=(\sum_{i=1}^{n}a_i)^2(\sum_{i=1}^{n}b_i)^2-(\sum_{i=1}^{n}a_ib_i)^2\) 。

2.2 范德蒙德卷积公式

在数量为 \(n+m\) 的堆中选 \(k\) 个元素，和分别在数量为 \(n、m\) 的堆中选 \(i、k-i\) 个元素的方案数是相同的，即\(\displaystyle{\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}}\) ；

变体：

\(\sum_{i=0}^k C_{i+n}^{i}=C_{k+n+1}^{k}\) ；
\(\sum_{i=0}^k C_{n}^{i}*C_m^i=\sum_{i=0}^k C_{n}^{i}*C_m^{m-i}=C_{n+m}^{n}\) 。

2.3 卡特兰数

Catalan 数列 \(H_n\) 可以应用于以下问题：

有 \(2n\) 个人排成一行进入剧场。入场费 5 元。其中只有 \(n\) 个人有一张 5 元钞票，另外 \(n\) 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
有一个大小为 \(n\times n\) 的方格图左下角为 \((0, 0)\) 右上角为 \((n, n)\)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 \(y=x\) 上方（但可以触碰）的情况下到达右上角有多少可能的路径？
在圆上选择 \(2n\) 个点，将这些点成对连接起来使得所得到的 \(n\) 条线段不相交的方法数？
对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
一个栈（无穷大）的进栈序列为 \(1,2,3, \cdots ,n\) 有多少个不同的出栈序列？
\(n\) 个结点可构造多少个不同的二叉树？
由 \(n\) 个 \(+1\) 和 \(n\) 个 \(-1\) 组成的 \(2n\) 个数 \(a_1,a_2, \cdots ,a_{2n}\)，其部分和满足 \(a_1+a_2+ \cdots +a_k \geq 0~(k=1,2,3, \cdots ,2n)\)，有多少个满足条件的数列？

其对应的序列为：

\(H_0\)	\(H_1\)	\(H_2\)	\(H_3\)	\(H_4\)	\(H_5\)	\(H_6\)	...
1	1	2	5	14	42	132	...

2.3.1 递推式

该递推关系的解为：

\[ H_n = \frac{\binom{2n}{n}}{n+1}(n \geq 2, n \in \mathbf{N_{+}}) \]

关于 Catalan 数的常见公式：

\[ H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases} \]

\[ H_n = \frac{H_{n-1} (4n-2)}{n+1} \]

\[ H_n = \binom{2n}{n} - \binom{2n}{n-1} \]

2.3.2 路径计数问题

非降路径是指只能向上或向右走的路径。

从 \((0,0)\) 到 \((m,n)\) 的非降路径数等于 \(m\) 个 \(x\) 和 \(n\) 个 \(y\) 的排列数，即 \(\dbinom{n + m}{m}\)。
从 \((0,0)\) 到 \((n,n)\) 的除端点外不接触直线 \(y=x\) 的非降路径数：

先考虑 \(y=x\) 下方的路径，都是从 \((0, 0)\) 出发，经过 \((1, 0)\) 及 \((n, n-1)\) 到 \((n,n)\)，可以看做是 \((1,0)\) 到 \((n,n-1)\) 不接触 \(y=x\) 的非降路径数。

所有的的非降路径有 \(\dbinom{2n-2}{n-1}\) 条。对于这里面任意一条接触了 \(y=x\) 的路径，可以把它最后离开这条线的点到 \((1,0)\) 之间的部分关于 \(y=x\) 对称变换，就得到从 \((0,1)\) 到 \((n,n-1)\) 的一条非降路径。反之也成立。从而 \(y=x\) 下方的非降路径数是 \(\dbinom{2n-2}{n-1} - \dbinom{2n-2}{n}\)。根据对称性可知所求答案为 \(2\dbinom{2n-2}{n-1} - 2\dbinom{2n-2}{n}\)。
从 \((0,0)\) 到 \((n,n)\) 的除端点外不穿过直线 \(y=x\) 的非降路径数：

用类似的方法可以得到：\(\dfrac{2}{n+1}\dbinom{2n}{n}\)

2.4 斐波那契数列

通项公式：\(F_n=\dfrac{1}{\sqrt 5}* \Big[ \Big( \dfrac{1+\sqrt 5}{2} \Big)^n - \Big( \dfrac{1-\sqrt 5}{2} \Big)^n \Big]\) 。

直接结论：

卡西尼性质：\(F_{n-1} * F_{n+1}-F_n^2=(-1)^n\) ；
\(F_{n}^2+F_{n+1}^2=F_{2n+1}\) ；
\(F_{n+1}^2-F_{n-1}^2=F_{2n}\) （由上一条写两遍相减得到）；
若存在序列 \(a_0=1,a_n=a_{n-1}+a_{n-3}+a_{n-5}+...(n\ge 1)\) 则 \(a_n=F_n(n\ge 1)\) ；
齐肯多夫定理：任何正整数都可以表示成若干个不连续的斐波那契数（ \(F_2\) 开始）可以用贪心实现。

求和公式结论：

奇数项求和：\(F_1+F_3+F_5+...+F_{2n-1}=F_{2n}\) ；
偶数项求和：\(F_2+F_4+F_6+...+F_{2n}=F_{2n+1}-1\) ；
平方和：\(F_1^2+F_2^2+F_3^2+...+F_n^2=F_n*F_{n+1}\) ；
\(F_1+2F_2+3F_3+...+nF_n=nF_{n+2}-F_{n+3}+2\) ；
\(-F_1+F_2-F_3+...+(-1)^nF_n=(-1)^n(F_{n+1}-F_n)+1\) ；
\(F_{2n-2m-2}(F_{2n}+F_{2n+2})=F_{2m+2}+F_{4n-2m}\) 。

数论结论：

\(F_a \mid F_b \Leftrightarrow a \mid b\) ；
\(\gcd(F_a,F_b)=F_{\gcd(a,b)}\) ；
当 \(p\) 为 \(5k\pm 1\) 型素数时，\(\begin{cases} F_{p-1}\equiv 0\pmod p \\ F_p\equiv 1\pmod p \\ F_{p+1}\equiv 1\pmod p \end{cases}\) ；
当 \(p\) 为 \(5k\pm 2\) 型素数时，\(\begin{cases} F_{p-1}\equiv 1\pmod p \\ F_p\equiv -1\pmod p \\ F_{p+1}\equiv 0\pmod p \end{cases}\) ；
\(F(n)\%m\) 的周期 \(\le 6m\) （ \(m=2\times 5^k\) 时取到等号）；
既是斐波那契数又是平方数的有且仅有 \(1,144\) 。

快速倍增法（比矩阵乘常数小）：

pair<int, int> fib(int n) { // O(logn)返回F(n),F(n+1)
  if (n == 0) return {0, 1};
  auto p = fib(n >> 1);
  int c = p.first * (2 * p.second - p.first);
  int d = p.first * p.first + p.second * p.second;
  if (n & 1)
    return {d, c + d};
  else
    return {c, d};
}

2.5 约瑟夫问题

n 个人标号 \(0,1,\cdots, n-1\)。逆时针站一圈，从 \(0\) 号开始，每一次从当前的人逆时针数 \(k\) 个，然后让这个人出局。问最后剩下的人是谁。

2.5.1 线性算法

设 \(J_{n,k}\) 表示规模分别为 \(n,k\) 的约瑟夫问题的答案。我们有如下递归式

\[ J_{n,k}=(J_{n-1,k}+k)\bmod n \]

这个也很好推。你从 \(0\) 开始数 \(k\) 个，让第 \(k-1\) 个人出局后剩下 \(n-1\) 个人，你计算出在 \(n-1\) 个人中选的答案后，再加一个相对位移 \(k\) 得到真正的答案。这个算法的复杂度显然是 \(\Theta (n)\) 的。

int josephus(int n, int k) {
  int res = 0;
  for (int i = 1; i <= n; ++i) res = (res + k) % i;
  return res;
}

2.5.2 对数算法

对于 \(k\) 较小 \(n\) 较大的情况，本题还有一种复杂度为 \(\Theta (k\log n)\) 的算法。

考虑到我们每次走 \(k\) 个删一个，那么在一圈以内我们可以删掉 \(\left\lfloor\frac{n}{k}\right\rfloor\) 个，然后剩下了 \(n-\left\lfloor\frac{n}{k}\right\rfloor\) 个人。这时我们在第 \(\left\lfloor\frac{n}{k}\right\rfloor\cdot k\) 个人的位置上。而你发现它等于 \(n-n\bmod k\)。于是我们继续递归处理，算完后还原它的相对位置。还原相对位置的依据是：每次做一次删除都会把数到的第 \(k\) 个人删除，他们的编号被之后的人逐个继承，也即用 \(n-\left\lfloor\frac{n}{k}\right\rfloor\) 人环算时每 \(k\) 个人即有 \(1\) 个人的位置失算，因此在得数小于 \(0\) 时，用还没有被删去 \(k\) 倍数编号的 \(n\) 人环的的 \(n\) 求模，在得数大于等于 \(0\) 时，即可以直接乘 \(\frac{k}{k-1}\), 于是得到如下的算法：

int josephus(int n, int k) {
  if (n == 1) return 0;
  if (k == 1) return n - 1;
  if (k > n) return (josephus(n - 1, k) + k) % n;  // 线性算法
  int res = josephus(n - n / k, k);
  res -= n % k;
  if (res < 0) res += n;  // mod n
  else res += res / (k - 1);  // 还原位置
  return res;
}

2.6 格雷码

int g(int n) { return n ^ (n >> 1); }

2.6.1 通过格雷码构造原数（逆变换）

接下来我们考虑格雷码的逆变换，即给你一个格雷码 \(g\)，要求你找到原数 \(n\)。我们考虑从二进制最高位遍历到最低位（最低位下标为 \(1\)，即个位；最高位下标为 \(k\)）。则 \(n\) 的二进制第 \(i\) 位与 \(g\) 的二进制第 \(i\) 位 \(g_i\) 的关系如下：

\[ \begin{aligned} n_k &= g_k \\ n_{k-1} &= g_{k-1} \oplus n_k &&= g_k \oplus g_{k-1} \\ n_{k-2} &= g_{k-2} \oplus n_{k-1} &&= g_k \oplus g_{k-1} \oplus g_{k-2} \\ n_{k-3} &= g_{k-3} \oplus n_{k-2} &&= g_k \oplus g_{k-1} \oplus g_{k-2} \oplus g_{k-3} \\ &\vdots\\ n_{k-i} &=\displaystyle\bigoplus_{j=0}^ig_{k-j} \end{aligned} \]

int rev_g(int g) {
  int n = 0;
  for (; g; g >>= 1) n ^= g;
  return n;
}

2.7 错位排列

2.7.1 定义

错位排列（derangement）是没有任何元素出现在其有序位置的排列。即，对于 \(1\sim n\) 的排列 \(P\)，如果满足 \(P_i\neq i\)，则称 \(P\) 是 \(n\) 的错位排列。

例如，三元错位排列有 \(\{2,3,1\}\) 和 \(\{3,1,2\}\)。四元错位排列有 \(\{2,1,4,3\}\)、\(\{2,3,4,1\}\)、\(\{2,4,1,3\}\)、\(\{3,1,4,2\}\)、\(\{3,4,1,2\}\)、\(\{3,4,2,1\}\)、\(\{4,1,2,3\}\)、\(\{4,3,1,2\}\) 和 \(\{4,3,2,1\}\)。错位排列是没有不动点的排列，即没有长度为 1 的循环。

错位排列数列的前几项为 \(0,1,2,9,44,265\)（OEIS A000166）。

2.7.2 递推的计算

错位排列数满足递推关系：

\[ D_n=(n-1)(D_{n-1}+D_{n-2}) \]

这里也给出另一个递推关系：

\[ D_n=nD_{n-1}+{(-1)}^n \]

2.7.3 其他关系

错位排列数有一个简单的取整表达式，增长速度与阶乘仅相差常数：

\[ D_n=\begin{cases} \left\lceil\frac{n!}{\mathrm{e}}\right\rceil, & \text{if }n\text{ is even}, \\ \left\lfloor\frac{n!}{\mathrm{e}}\right\rfloor, & \text{if }n\text{ is odd}. \end{cases} \]

随着元素数量的增加，形成错位排列的概率 P 接近：

\[ P=\lim_{n\to\infty}\frac{D_n}{n!}=\frac{1}{\mathrm{e}} \]

2.8 康托展开

\(O(n\log{n})\) 求出一个排列在所有长度为 \(n\) 的排列中的字典序排名。

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MOD = 998244353;
constexpr int N = 1e6 + 5;
int n, x, d[N], fac[N], ans;
void add(int i, int x) {
    for (; i <= n; i += (i & -i)) d[i] += x;
}
int query(int i, int s = 0) {
    for (; i > 0; i -= (i & -i)) s += d[i];
    return s;
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        d[i] = (i & -i);                 // O(n) 建树
        fac[i] = (fac[i - 1] * i) % MOD;  // 预处理阶乘
    }
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        add(x, -1);
        ans = (ans + query(x) * fac[n - i] % MOD) % MOD;
    }
    cout << ans + 1 << '\n';
}

2.9 逆康托展开

由于 \(n\) 不会超过20（否则没法处理阶乘），这里提供暴力做法，复杂度 \(O(n^2)\)。

#define int long long
constexpr int N = 21;
int fac[N]; // 预处理一下阶乘表
vector<int> get_inv_cantor(int n, int k) { // k从0开始
    vector<int> perm;
    vector<bool> used(n + 1, false);
    for (int i = n; i >= 1; --i) {
        int order = k / fac[i - 1];
        k %= fac[i - 1];
        for (int j = 1; j <= n; ++j) {
            if (used[j]) continue;
            if (order == 0) {
                perm.push_back(j);
                used[j] = true;
                break;
            }
            order--;
        }
    }
    return perm;
}

2.10 第二类斯特林数（Stirling Number）

第二类斯特林数（斯特林子集数）\(\begin{Bmatrix}n\\ k\end{Bmatrix}\)，也可记做 \(S(n,k)\)，表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个互不区分的非空子集的方案数。

2.10.1 递推式

\[ \begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix} \]

边界是 \(\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]\)。

2.10.2 通项公式

\[ \begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} \]

2.10.3 同一行第二类斯特林数的计算

「同一行」的第二类斯特林数指的是，有着不同的 \(i\)，相同的 \(n\) 的一系列 \(\begin{Bmatrix}n\\i\end{Bmatrix}\)。求出同一行的所有第二类斯特林数，就是对 \(i=0..n\) 求出了将 \(n\) 个不同元素划分为 \(i\) 个非空集的方案数。

根据上面给出的通项公式，卷积计算即可。该做法的时间复杂度为 \(O(n \log n)\)。