天边的生活の博客

基本计数原理

加法原理：解决一件事情，有 $m$ 种方法。每种方法有 $a_i$ 种选择，总方案数为 $\sum\limits^m_{i=1}a_i$。

乘法原理：解决一件事情，有 $n$ 个步骤。每个步骤有 $a_i$ 中选择，总方案数为 $\prod\limits^m_{i=1}a_i$。

排列与组合

将 $n$ 个元素选出来 $m$ 个构成一个排列，方案数为 $A_n^m=\dfrac{n!}{(n-m)!}$。

将 $n$ 个元素选出来 $m$ 个构成一个组合，方案数为 $C_n^m=\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}=\dfrac{A_n^m}{m!}$。

多重集的排列数与组合数

多重集的排列是指 $m$ 种元素，第 $i$ 种元素的个数为 $a_i,\sum\limits_{i=1}^m=n$，其全排列的方案数为 $\dfrac{n!}{a_1!a_2!\dots a_m!}$。

多重集的组合数：
设有 $m$ 种元素，第 $i$ 种元素的个数为 $a_i$。取共计 $r$ 个元素构成集合，且 $r\le a_i(i\in[1,n])$，其组合数为 $C^{m-1}_ {r+m-1}$。（隔板法）

组合数的常用性质：

性质 $1$：$C^0_n+C^1_n+C^2_n+\dots+C^n_n=2^n$。

性质 $2$：$C^m_n=C^{n-m}_ n$。

性质 $3$：$C^m_n=C^{m-1}_ {n-1}+C^m_{n-1}$。（即杨辉三角。DP 时设初始状态 $dp_{0,0}=1$。）

杨辉三角

图像：

二项式定理

$(a+b)^n=\sum\limits^n_{i=0}C^i_n\times a^i\times b^{n-i}$。

组合数的计算

方法 $1$：利用杨辉三角递推计算，时间复杂度 $O(n\times m)$。

方法 $2$：用公式。注意将除法变成乘法逆元（即 $C^m_n=\dfrac{n!}{m!(n-m)!}=n!\times \operatorname{inv}(m!)\times\operatorname{inv}((n-m)!)$） 。时间复杂度 $O(n)$。（限制：$m!$ 和 $(n-m)!$ 均与模数 $p$ 互质。）

乘法逆元

对于正整数 $a,p$，若 $a$ 与 $p$ 互质，那么当 $a\times x\equiv1\pmod p$ 时，称 $a$ 和 $x$ 在模 $p$ 意义下互为乘法逆元。记为 $\operatorname{inv}(a)=x,\operatorname{inv}(x)=a$ 或 $a^{-1}=x$。

费马小定理：对于正整数 $a,p$（$p$ 为质数），且 $a$ 与 $p$ 互质，那么 $a^{p-1}\equiv\pmod p$。

进一步可以得到 $a\times a^{p-2}\equiv1\pmod p$。

那么 $a$ 在模 $p$ 意义下的一个乘法逆元即为 $a^{p-2}$。

错位排序问题

有 $n$ 个位置和 $n$ 个小球，编号为 $1\sim n$，所有小球 $i$ 不放入位置 $i$ 的方案总数 $dp_n=(i-1)\times(dp_{i-1}+dp_{i-2})$，初始 $dp_1=0,dp_2=1$。

证明：
1.若前 $n-1$ 个小球已经全部全部错排，那么第 $n$ 个球和任意的前 $n-1$ 个小球交换位置即可。共 $n-1\times dp_{n-1}$ 种方案。

2.若前 $n-1$ 个小球恰有一个未错排，那么第 $n$ 个球和这个球交换位置即可。未错排的小球有 $n-1$ 种可能，共计 $n-1\times dp_{i-2}$ 种方案。

3.若前 $n-1$ 个小球有超过一个小球未错排，此时再加一个球不存在方案。

卢卡斯（Lucas)定理

对于正整数 $n,m,p$，若 $1\le m\le n$ 且 $p$ 为质数，那么 $C^m_n\bmod p=C^{m\bmod p}_ {n\bmod p}\times C^{\frac{m}{p}}_ {\frac{n}{p}}\bmod p$。

使用场景

求组合数 $C^m_n$ 时，若 $m$ 很大导致 $m!$ 或 $(n-m)!$ 是 $p$ 的倍数，那么无法通过求逆元得到结果。此时适用卢卡斯定理。

例题：P3807【模板】卢卡斯定理/Lucas 定理。

注意到，卢卡斯定理的本质是将 $n$ 和 $m$ 转为 $p$ 进制得到 $a_{t-1},a_{t-2},\dots,a_0$ 和 $b_{t-1},b_{t-2},\dots,b_0$。

那么我们可以得到 $C^m_n\bmod p=\prod\limits_{i=0}^{t-1}C^{b_i}_ {a_i}\bmod p$。

Prufer 序列

Prufer 序列是一种树形结构和序列相互映射的规则。（例如 DFS 序。）

与其他序列的区别

DFS 序：将一棵子树映射为一段连续的区间。

欧拉序：可应用为二叉搜索树。

Prufer 序列是和树的双向唯一映射。这意味着可以有树得到唯一的 Prufer 序列，反之也可以唯一的得到一棵树。

同时，Prufer 序列也包含了所有节点的度数和连接关系。

使用场景

可以将构造树转化为构造序列，将统计树的信息转化为统计序列的信息，将树上 DP 转化为序列 DP。

如何得到 Prufer 序列

1.统计树上所有结点的度数 $deg_i$；

2.找到所有度数为 $1$ 的节点中编号最小的结点 $x$。

3.令 Prufer 序列 $p_i=fa_x$，将 $deg_{fa_x}\gets deg_{fa_x} - 1$。

4.重复步骤 2-3，直到剩余两个点时结束。

Prufer 序列的性质

1.结点 $x$ 在 Prufer 序列中出现的次数 $y$ 满足 $y+1=deg_x$。

2.编号最大点 $n$ 一定是剩下的 $2$ 个结点之一。

3.对于一个 $n$ 个点的完全图，其生成树的方案数为 $n^{n-2}$。

4.对于 $n$ 个点的无根树，其树的方案数为 $n^{n-2}$。

5.对于 $n$ 个点的有根树，其树的方案数为 $n^{n-1}$。

6.对于 $n$ 个结点，约定点 $i$ 的度数为 $d_i$，其满足条件的树的方案数为 $\dfrac{(n-2)!}{\prod\limits^n_{i=1}(d_i-1)!}$。

核心代码

void to_prufer(){//一般来说，在构造 prufer 序列的时候，我们会让结点 n 作为根节点。
  int x;
  for (int i = 1; i <= n; i++){
    if (deg[i] == 1){
      x = i;
      break;
    }
  }
  int l = x;
  for (int i = 1; i <= n - 2; i++){
    int f = fa[l];
    prufer[i] = f;
    deg[f]--;
    if (deg[f] == 1 && f < x){
      l = f;
      continue;
    }
    x++;
    while (deg[x] != 1){
      x++;
    }
    l = x;
  }
}

void to_tree(){
  for (int i = 1; i <= n; i++){
    deg[i] = 1;
  }
  for (int i = 1; i <= n - 2; i++){
    deg[prufer[i]]++;
  }
  int x;
  for (int i = 1; i <= n; i++){
    if (deg[i] == 1){
      x = i;
      break;
    }
  }
  int l = x;
  for (int i = 1; i <= n - 2; i++){
    int f = fa[l] = prufer[i];
    deg[f]--;
    if (deg[f] == 1 && f < x){
      l = f;
      continue;
    }
    x++;
    while (deg[x] != 1){
      x++;
    }
    l = x;
  }
  fa[l] = n;
}

卡特兰数(Catalan number)

它是一种数列，其通项公式的一种为：
$a_n=\dfrac{1}{n+1}\times C^n_{2n}(n\in[0,+\infty))$。

它的前几项数值为：$1,1,2,5,14,42,132,429\dots$。

增长幅度大约为 $O(4^n)$。

卡特兰数的递归定义式 $1$ 为：
$a_n=\sum\limits^{n-1}_ {i=0}a_i\times a_{n-i-1}$。

使用场景：递归定义式 $1$ 适用于 $n$ 不大的情况下求卡特兰数，其不用处理除法。（一般满足 $n\le 500$。）

理解：对于一个 $n$ 个点构成的二叉树，其形态有 $a_n$ 种。

递归定义式 $2$：
$a_n=a_{n-1}\times\dfrac{4n-2}{n+1}$。

组合定义式：
$a_n=C^n_{2n}-C^{n-1}_ {2n}=\dfrac{1}{n+1}\times C^n_ {2n}$。

例 $1$：01 排列问题

构造 $n$ 个 $0$ 和 $n$ 个 $1$ 共 $2\times n$ 个元素的数列，要求该数列的任意前缀 $0$ 的个数不少于 $1$ 的个数。求数列的方案数。

例 $2$：括号序列匹配

给定 $n$ 个左括号和 $n$ 个右括号，其合法的匹配括号序列的方案数为 $C^n_{2n}-C^{n-1}_ {2n}$。

例 $3$

给定 $n$ 个元素，编号为 $1\sim n$。其进出栈的不同方案数为卡特兰数。

例 $4$

给定 $n$ 条边的凸多边形，用 $n-3$ 条边将其划分成 $n-2$ 个三角形，其方案数为卡特兰数。

康托展开

定义

对于 $1\sim n$ 的全排列，建立排名和排列的双射。由排列映射到排名可以视为一种（双向）哈希。

原理

设有 $1\sim n$ 的某个排列 $p_1,p_2,\dots,p_n$，其排名应该为小于该排列的数量 $+1$.

那么这个排列的排名应该是 $(\sum\limits^n_{i=1}(n-i)!\times\sum\limits^n_{j=i+1}[p_j<p_i])+1$ 。

（自己画个图应该就能理解。）

不难发现其时间复杂度为 $O(n^2)$。不过可以使用树状数组等数据结构优化成 $O(n\log_2 n)$。

模板：洛谷 P5367 【模版】康托展开。

逆康托展开

首先可知 $n!>\sum\limits^{n-1}_ {i = 1}i\times i!$ 恒成立。

那么，假设一个 $n=4$ 的排列的排名为 $46$。根据定义，可以知道比这个排列小的排列由 $46-1=45$ 个。

那么比第 $1$ 位的数小的个数根据定义就是 $\left\lfloor\dfrac{45}{4!}\right\rfloor=1$。

然后 $45-1\times 4!=21$。以此类推就可以求出这个排列是 $[2,5,3,4,1]$。

代码（时间复杂度：$O(n^2)$）：

fact[0] = 1;
for (int i = 1; i <= n; i++){
  fact[i] = fact[i - 1] * i;
}

void decantor(int n, int x){//长度为 n 的排列的排名为 x
  x--;
  vector<int> tmp(n);//存储当前未出现在排列中的数字
  vector<int> a(n);//排列
  for (int i = 0; i < n; i++){
    tmp[i] = i + 1;
  }
  for (int i = 1; i <= n; i++){
    int p = x / fact[n - i];
    x %= fact[n - i];
    a[i - 1] = tmp[p];
    tmp.erase(lower_bound(tmp.begin(), tmp.end(), a[i - 1]));
  }
}