二进制状态压缩

集合回顾

集合的概念和特性

集合是数学中的一个基本的概念，通俗地理解，集合是由一些不重复的数据组成的。比如 ${1,2,3}$ 就是一个有三个元素组成的集合。

那么集合有一些特性，主要有以下三条：

  1. 确定性：任意给一个元素和一个集合，该元素 属于 或者 不属于 这个集合，二者必居其一，不允许有模棱两可的情况出现。
  2. 互异性：一个集合当中，任何两个元素都认为是 不相同 的，即每个元素只能出现一次。
  3. 无序性：一个集合当中，每个元素的地位都是相同的，元素之间是无序的。集合上面可以定义序关系，定义了序关系之后，元素之间就可以按照序关系排序。但是就集合本身的特性而言，元素之间没有必然的序。

集合和集合间的关系

然后来简单地回顾一下集合和集合之间的关系：

  1. 子集和真子集：设 $S,T$ 是两个集合，如果 $S$ 的所有元素都在 $T$ 内，则称 $S$ 是 $T$ 的子集。如果此时满足 $S,T$ 不相等，则称 $S$ 是 $T$ 的真子集。

  2. 空集：不包含任何元素的集合。

  3. 全集：在一个相对固定的范围内的所有元素的集合。

  4. 交集：既属于集合 $S$ 也属于集合 $T$ 的元素组成的集合。用 $S\cap T$ 表示。

  5. 并集：属于集合 $S$ 或者 $T$ 的元素组成的集合。用 $S\cup T$ 表示。

  6. 补集：设 $S$ 是全集，$T$ 是 $S$ 的子集，属于 $S$ 但不属于 $T$ 的所有元素组成的集合。用 $S-T$ 或者 $\sim T$ 表示。

容斥原理

容斥原理是在计数时，为了使重叠部分不被重复计算，没有遗漏部分，人们研究出一种新的计数方法。

这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。

集合 $S,T$ 的并集内元素的个数为：$Size(S) + Size(T) - Size(S\cap T)$。

具体应用：

一次期末考试，某班有 $15$ 人数学得满分，有 $12$ 人语文得满分，并且有 $4$ 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人。

分析：依题意，被计数的事物有语、数得满分两类，“数学得满分” 称为 “A 类元素”，“语文得满分” 称为 “B类元素”，“语、数都是满分” 称为 “C 类元素”，“至少有一门得满分的同学” 称为 “A 类和 B 类元素个数” 的总和。为 $15+12-4=23$。

集合的二进制表示

子集总个数

对于一个全集 $S={x_0,x_1,\cdots,x_{n-1}}$（$n$ 是集合 $S$ 的元素个数）的任意元素 $x_i$，根据我们了解过的集合的 确定性，有 $x_i$ 一定属于 或者 一定不属于 $S$ 的某一个子集。那么对于全集内的 $n$ 个元素而言，每一个元素都会有这么两种情况。由此我们可以得到，全集 $S$ 的不同的子集的个数是 $2^n$ 个。

二进制和集合关系

实际上，属于和不属于作为一对正反关系，我们便可以使用 $0$ 和 $1$ 去表示。一般来讲我们使用 $1$ 表示属于，$0$ 表示不属于。

你已经学过了搜索和动态规划，现在给你一个有三个元素的集合 $S={1,2,3}$，你怎么表示出这个集合的所有子集？

其实你可以很容易地使用一个三维数组 $a_{2,2,2}$，每一维分别表示某个子集是否分别包含这三个元素，然后你可以用这个数组去保存这个子集里面元素的和，积，最大值等等信息，例如数组表示子集内元素的和时：$a[1][0][1] = 1 + 3 = 4$。

那么如果这个集合包含 $20$ 个元素呢？或者干脆这个集合大小就不定呢？我们还是回到一开始的那个问题。

状态压缩和集合表示

实际上你还有一种解答的方式：我们不再使用一个三维数组，而是一个一维数组 $a_8$。我们看一下 $0\sim 7$ 在二进制下的表示方式：

  1. $0=0\times 2^2+0\times 2^1+0\times 2^0$
  2. $1=0\times 2^2+0\times 2^1+1\times 2^0$
  3. $2=0\times 2^2+1\times 2^1+0\times 2^0$
  4. $3=0\times 2^2+1\times 2^1+1\times 2^0$
  5. $4=1\times 2^2+0\times 2^1+0\times 2^0$
  6. $5=1\times 2^2+0\times 2^1+1\times 2^0$
  7. $6=1\times 2^2+1\times 2^1+0\times 2^0$
  8. $7=1\times 2^2+1\times 2^1+1\times 2^0$

对于每一个 $0\times 2^i$，代表着 $S_i$ 不在当前表示的子集里； $1\times 2^i$，代表着 $S_i$ 在当前表示的子集里。比如对于集合 $S={1,2,3}$，$a_5$ 就代表子集 $T={1,3}$。

二进制数位 2 1 0
二进制数值 1 0 1
选取的元素 3 - 1

这就是 状态压缩。我们将一个本来需要使用三维来表示的状态压缩到一维，虽然对占用空间大小的减少并没有任何实质性帮助，但是这样的方式会增加状态表示的 通用性（因为你也可以使用类似的方式去将更多维的状态进行压缩）。

当然表示一个集合的子集的方式其实是很多的，但是由于计算机内部位运算非常便捷，我们通常借助二进制和位运算完成集合的表示运算。

现在来看一个小问题：对于集合 $S={1,2,3,4,5,6}$，使用一维数组 $a$ 来代表 $S$ 的每个子集的元素和，$a_{53}$ 的值是多少？

从子集中提取元素

我们回到刚才的小问题。$a_{53}$ 用于表示集合 $S={1,2,3,4,5,6}$ 的一个子集，那么现在提出一个问题：

$S_3$ 是否包含于 $a_{53}$ 表示的子集中？

一个最显然的方式是将 $53$ 转化为二进制表示为 $110101$，结果发现表示 $2^3$ 那一位是 $0$，所以能够看出 $S_3$ 不包含于 $a_{53}$ 表示的子集中。

但是实际上我们不需要去真的把二进制表示转化出来，因为至始至终我们都只需要把表示 $2^3$ 那一位取出来即可。这时候我们就需要使用位运算了。那么有两种方式可以将 $2^3$ 那一位取出来：

  1. 53 & (1 << 3)
  2. (53 >> 3) & 1

如果我们将问题一般化：对于某个集合 $S$，一维数组 $a$ 用于表示 $S$ 的子集，那么 $a_i$ 表示的子集中是否包含 $S_j$ 的判断方式有两种：

  1. i & (1 << j)
  2. (i >> j) & 1

对于两种方式而言，如果不存在，表达式的值都为 $0$；反之，如果存在，则不为 $0$。当然如果存在的话，这两种方式算出来的值，是不一样的，第一种方式算出来的值是 $2^j$，而第二种方式算出来的值是 $1$。

集合间关系

我们已经探索完了单个集合和元素的关系，现在我们来看一看集合和集合之间的关系。

同样还是某个大小为 $n$ 的集合 $S$，一维数组 $a$ 用于表示 $S$ 的子集。现在有两个子集 $a_i,a_j$：

  1. 全集：全集在这里是 $S$ 的所有元素组成的集合，所以全集的表示方式为 $a_{2^0+2^1\cdots+2^{n-1}}$ 即 $a_{2^n-1}$。
  2. 空集：空集内不包含任何元素，所以用 $a_0$ 表示。
  3. 交集：$a_i$ 和 $a_j$ 的交集可以用 $a_{i\&j}$ 表示。
  4. 并集：$a_i$ 和 $a_j$ 的并集可以用 $a_{i\mid j}$ 表示。
  5. 补集：$a_i$ 关于全集 $S$ 的补集可以用 $a_{2^n-1-i}$ 表示。
  6. 包含：$a_j$ 包含于 $a_i$ 当且仅当 $i\&j=j$。

子集快速枚举

还记得刚才的包含关系吗？根据集合间的包含关系，我们可以得到一种简单粗暴的枚举 $a_i$ 的子集的方法：

for (int j = 0; j < (1 << n); j++) {
    if ((j & i) == j) {
        //具体操作
    }
}

但是我们知道枚举法的大忌就是去计算一些很明显没有枚举意义的部分。那么有没有办法来优化上面的枚举呢？我们再来看看下面这段代码：

for (int j = i; j; j = ((j - 1) & i)) {
    //具体操作
}

把 $j$ 输出来会发现，所有的 $j$ 都满足 $j\&i=j$，实际上这就是枚举 $a_i$ 的子集的一种较快的方式。

例题选讲

例题：得到整数 x

对于 $n$ 个互不相同的正整数，要从这 $n$ 个整数当中无重复地选取任意个数，使得选出的整数之和为 $x$。现在你需要求出总共有多少种选取方案。

解析

实际上你应该已经见过这个题了，在讲深度优先搜索的时候也出现了这道例题，但是当时我们是使用搜索算法完成的。这一次我们换一种做法。

实际上问题可以转化为集合 $S={S_0,S_1,\cdots,S_{n-1}}$ 当中，元素和为 $x$ 的不同子集的个数。

一个大小为 $n$ 的集合的不同的子集的个数是 $2^n$ 个，按照集合的表示方式，子集的编号是 $0\sim 2^n-1$，挨个枚举然后取出每个子集当中有哪些元素，求和，然后检验元素和是否为 $x$，统计个数就解决了。

例题：李白饮酒

一天，李白提着酒壶，从家里面出发，酒壶里面一开始有两斗酒。

李白一路上会遇到 $5$ 家酒馆和 $10$ 处花丛。李白每到达一个酒馆，就将他壶里面的酒的存量翻倍；每到达一处花丛，便喝一斗酒。已知李白最后一次移动走到了一处花丛中，并正好喝光了他的酒。请你算出李白有多少种满足要求的遇到花丛和酒馆的情况。

解析

我们可以发现，李白到达的地点一定是花丛或者酒馆的其中一个，所以可以用 $0$ 表示李白当前到了花丛，用 $1$ 表示李白当前到了酒馆。

李白总共按顺序到达了 $15$ 个地点，那么用一个 $15$ 位二进制数（可以有前导 $0$）就可以表示李白按顺序到达的地点。

例如 $000000000011111$ 代表李白先依次到达 $10$ 个花丛，然后依次到达 $5$ 个酒馆。

那么分别枚举 $0\sim 2^{15}-1$，你需要进行如下的判断：

  1. 最后一个地点是不是花丛；
  2. 李白是否是到达了 $5$ 个酒馆和 $10$ 个花丛；
  3. 李白是否是 正好喝完 酒（即到达第 $14$ 个地点并结算之后还剩下一升酒）。

按位构造

我们知道，对数做位运算的时候，每一个二进制位是 独立的，所以在主要涉及位运算的问题中，我们会考虑按位来进行思考。

一般来讲，我们都会从 最高位 开始思考，然后看 次高位，一直到 最低位。

在计算最高位的情况之前，首先确认最大的位数（可包含前导 $0$）。

对于这道题目而言，$r\le 2^{61}-1$，所以很明显地，答案最多只有 $61$ 位，最高位表示的是 $2^{60}$。

接下来我们来思考答案的 最高位 的值。由于这道题做的是 按位与 运算，很明显只要所有的运算对象中有一个最高位是 $0$，那么最高位就是 $0$。$l$ 作为运算对象的最小值，很明显是最高位里面值最有可能是 $0$ 的那一个，所以对 $l$ 进行判断即可。

然后来求 次高位。我们还是来看次高位为 $0$ 的情况。此时只需要对 $l$ 和 $r$ 的次高位都为 $1$ 的场合进行讨论（因为其他时候答案的次高位一定是 $0$，只需要把 $l,r$ 按位与即可）

当 $l$ 和 $r$ 的次高位都为 $1$，但是 $[x,y]$ 和它们之间所有整数 按位与 的结果次高位上是 $0$ 的时候，很明显，从 $l$ 到 $r$ 这 $r-l+1$ 个整数的二进制形式在次高位上的变化应该是 $1\rightarrow0\rightarrow1$。

注意到 $1\rightarrow0$ 的情况，很明显是在 $[l,r]$ 之间的某个数 $x$ 变成 $x+1$ 之后，次高位上发生了 进位，而进位会导致最高位值的变化。也就是说，当 $l$ 和 $r$ 的最高位不同时，无论次高位如何取值，答案的次高位一定为 $0$。

实际上，在次高位发生进位的时候，比次高位更低的位一定也同时发生了进位（因为数的变化每一次都是加 $1$，所以连续的进位一定是从最低位开始的）。比如说从 $7$ 变成 $8$：

\[\displaystyle (0111)_2\rightarrow(1000)_2\]

$2^2$ 那一位发生了进位，而 $2^1,2^0$ 那两位也同时进位了。

针对次高位的讨论结束了，我们总结出了上一页的信息。接下来我们需要对相关结论进行扩展，由此我们其实就可以得到这道题的做法了：

实际上样例 $l=5,r=7$ 里面就出现了第三种情况。

builtin 函数

GCC 提供了一系列的 builtin 函数，可以实现一些简单快捷的功能来方便程序编写，另外，很多 builtin 函数可用来优化编译结果。这些函数以__builtin_作为函数名前缀。

在这里我们提供一些跟二进制相关的函数：

int p = __builtin_ffs(x);

$2^{p-1}$ 即为 $x$ 作为二进制表示时的最低位 $1$ 实际表示的值，例如：__builtin_ffs(6) = 2。

int p = __builtin_ctz(x);

$p$ 表示 $x$ 二进制表示时末尾 $0$ 的个数。例如：__builtin_ctz(6) = 1。

int p = __builtin_popcount(x);

$p$ 表示 $x$ 二进制表示时值为 $1$ 的位数的个数。例如：__builtin_popcount(6) = 2。

int p = __builtin_clz(x);

$p$ 表示 $x$ 二进制表示时前导 $0$ 的个数。$x=0$ 时结果未定义。__builtin_clz(6) = 29。

需要注意的是，这些函数中，$x$ 的类型都是 unsigned int，即 $32$ 位 无符号 整数类型。

状态压缩 DP

状态压缩搜索

你是否还记得这个问题：

蒜头君在一个迷宫里面，现在需要从迷宫中走出去。迷宫的一些格子里面有钥匙，而某些相邻的格子中间有需要使用这些钥匙的其中一个打开的门。现在给你整个迷宫的结构和你的起点，然后你需要求解蒜头君最少需要走多少步才能离开这个迷宫（假设保证了蒜头君一定能走出去）。

如果只是一个简单的迷宫（不需要使用钥匙的），相信你能够使用 dfs 或者 bfs 很快地搞定。如果是带钥匙的情况，只有一把钥匙的时候也很简单，那就在表示状态的数组上再加一维表示现在蒜头君手头有没有钥匙就好了。

如果有很多把不同的钥匙呢？实际上我们可以将这些钥匙作为一个 集合，比如说有 $8$ 把钥匙，那么我们可以构造这么一个集合 $S={key_0,key_1,\cdots,key_7}$。而蒜头君手上所拥有的钥匙的集合一定是 $S$ 的一个子集，如果需要判断蒜头君能否通过一扇门，就看当前状态下拥有的钥匙的集合（$state$）里面是否包含需要用于开门的那把钥匙就行了：$state \in S$。

在进行抽象的搜索的时候，我们要花很多精力去研究状态的表示方式。有时候我们便需要使用状态压缩之后的二进制数表示状态或者状态的某一维。而借助于 集合 这一概念能使你更好的理解并运用这种状态压缩的方式。

对于每把钥匙，共有两种状态：有或没有，所以可以使用 $1/0$ 表示有没有该钥匙，因为只有 $1/0$，所以可以使用二进制表示拥有的钥匙状态。即：如果有第 $i$ 把钥匙，那么二进制的第 $i$ 位（最低位为第 $1$ 位）为 $1$，否则为 $0$。

若当前状态为 $state$，可以对它进行二进制操作：

  1. 当前获得第 $i$ 把钥匙：$state = (1 « i)$。
  2. 是否有第 $i$ 把钥匙：if (state & (1 << i)){/* 有第 i 把钥匙 */}

注：使用二进制压缩状态时，种类数一般很少，因为二进制的位数有限。

接下来我们再来看一道例题。

关灯问题

题目描述

有 $n$ 盏灯，每盏灯的编号是 $0\sim n-1$，每盏灯可以是亮的或者是暗的。

第 $i$ 盏开关管 $c_i$ 盏灯，分别是 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, c_i}$。即每摁一次第 $i$ 盏开关，那么这 $c_i$ 盏灯都会切换当前的状态（由亮至暗，由暗至亮）。

初始情况是所有灯都亮着，问最少需要多少次按开关的操作才能把所有灯变暗。

解析

我们依然可以将这 $n$ 盏灯当做一个集合 $S={l_0,l_1,\cdots l_{n-1}}$。那么无论我们摁了多少次开关，亮着的灯所组成的集合都是 $S$ 的子集。

初始的时候，这个集合和 $S$ 是等同的，因为所有灯都亮着，而我们的目标是所有灯都灭了，也就是集合变成了空集。那么我们便可以用 $2^n-1$ 去表示初始状态（二进制表示状态，$n$ 盏亮着的灯，状态表示：$(\overbrace{1,\cdot\cdot\cdot,1}^{n})_2 = 2^n - 1$），而用 $0$ 表示目标状态。

那么现在我们来看看搜索算法处于某个状态 $x$ 的时候，摁下第 $i$ 个开关的时候会发生什么。对于这 $c_i$ 盏灯里面的任何一盏，如果属于状态 $x$ 所对应的集合，那么在摁下开关之后会熄灭；如果不属于状态 $x$ 所对应的集合，那么在摁下开关之后会开启。

如果我们用 $0$ 和 $1$ 来概括，那就是 $0$ 变成 $1$，而 $1$ 变成 $0$。那么我们可以这么做去算出状态 $x$ 摁下第 $i$ 个开关之后会变成的状态 $dx$：

int dx = x;
for (int j = 1; j <= c[i]; j++) {
    dx ^= (1 << a[i][j]);
}

当然其实我们还有一种更快的方式，那就是先将第 $i$ 个开关 $x$ 需要异或的数的值预处理出来。

temp[i] = 0;
for (int j = 1; j <= c[i]; j++) {
    temp[i] ^= (1 << a[i][j]);
}

那么这样状态 $x$ 摁下第 $i$ 个开关之后会变成的状态就可以直接使用 $x$ $\hat{}$ $temp_i$ 表示了。

搜索过程不再赘述。

状态压缩动态规划

例题：传递物品

$n$ 个人在做传递物品的游戏，编号为 $0\sim n - 1$。

游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人，即物品只能经过同一个人一次。而且每次传递过程都有一个代价；第 $i$ 个人将物品传给第 $j$ 个人的代价是 $a_{i,j}$。

求当物品经过所有 $n$ 个人后，整个过程中最小的总代价是多少。

解析

我们将这 $n$ 个人当做一个集合 $S={man_0,man_1,\cdots,man_{n-1}}$，那么已经接过物品的人组成的集合一定是 $S$ 的子集。

我们令 $f_{i,j}$ 为二进制压缩状态 $i$ 所对应的子集内的人都 接过 了物品，$man_j$ 是 最后一个 接的，且子集外的人都 没有接过 物品时的最小代价。那么这个子集内除了 $man_j$ 的每一个人都可以成为把物品递给 $man_j$ 的人，枚举一下取一个最优值就好了。然后来看看转移方程：

\[\displaystyle f_{i,j} = min \{f_{i-2^j,k} + min\{a_{k,j}\}\}\] \[\displaystyle i\&2^k=2^k,i\&2^j=2^j,j\ne k\]

最后来思考初始状态和终末状态。开始时物品可以在任意一人手上，那么初始的集合可能是 ${man_0},{man_1},\cdots,{man_{n-1}}$，对应的状态则是 $1,2,\cdots,2^{n-1}$。而最终物品会经过所有人，所以终末状态是 $2^n-1$。

那么我们的边界条件就是：

\[\displaystyle f_{2^k,k}=0(0\le k\le n - 1),f_{i,j} = inf(i\ne 2^j)\]

最后取出的答案是 $min{f_{2^n-1,i}}(0\le i \le n-1)$。

旅行商问题

例题：旅行商问题

旅行商问题，即 TSP 问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访 $n$ 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP 是一道经典的 NP- 完全问题，在规模比较小的时候可以用动态规划求解。

有 $n$ 个城市，两两之间均有道路直接相连。给出每个城市 $i$ 和 $j$ 之间的道路长度 $dist(i,j)$，求一条从城市 $0$ 出发，经过其他城市一次 且仅一次，最后回到起点的路线，使得经过的道路总长度最短。$3\le n \le16$，城市编号为 $0\sim n-1$。

解析

我们将这 $n$ 个城市当做一个集合 $S={city_0,city_1,\cdots,city_{n-1}}$，那么已经到达的城市组成的集合一定是 $S$ 的子集。

实际上这个题和传递物品那道题的唯一区别在于，当你访问了路径上最后一个城市之后还需要返回最开始的城市。

试着自己写下状态和转移的方程吧。

令 f[i][j] 表示当前经过的城市集合的状态为 $i$，并且最后到达的是城市 $j$。

初始状态：

\[f[i][j] = \begin{cases}0 & i = 1\ \text{且} \ j = 0 \inf & \text{其他}\end{cases}\]
状态转移方程：$f[i (1 « k)] = \min(f[i (1 « k)], f[i][j] + f[j][k])$ 其中 $i \& (1«j) \neq 0, i \& (1«k) == 0$。

因为最后还需要回到起点，所以还需要枚举最后到达的是城市 $i$，总长度还需要再加上从 $i$ 城市到达 $0$ 城市的的长度，维护最小值。

for (int i = 0; i < n; i++) {
    ans = min(ans, f[(1 << n) - 1][i] + dis[i][0]);
}

例题：方格取数问题

给定一个 $n \times m$ 的矩阵，行数和列数都不超过 $20$，其中有些格子可以选，有些格子不能选。现在你需要从中选出尽可能多的格子，且保证选出的所有格子之间不相邻（没有公共边）。

例如下面这个矩阵（$2 \times 3$ 的矩阵 $map$，可选的位置标记为 $1$，不可选的位置标记为 $0$）：

1 1 1
0 1 0

最多可选 $3$ 个互不相邻的格子，方案如下（选中的位置标记为x）：

x 1 x
0 x 0
解析

我们可以自上而下，每一行分别选择格子。

那么对于每一行，我们可以将这一行的所有格子当做一个集合 $S={node_{0},node_{1},\cdots,node_{m-1}}$。那么被选的格子组成的集合一定是 $S$ 的子集。所有不能选择的格子也能组成一个子集，我们将这个子集所对应的状态进行一个预处理，对于第 $i$ 行，假设叫 $zero_i$。

这道题还加入了 子集是否合法 这一元素。那么对于第 $i$ 行的某种选格子的状态 $x$，按照题目的要求，我们需要从两个标准去判断：

  1. 不能覆盖到不能选的格子。即需要满足 $zero_i\&x=0$
  2. 选出来的格子不能相邻。即需要满足 $x\&(2\times x)=0$。

根据这样两个条件，我们可以分别得到每一行所有的合法选取方式，并且可以用动态数组存下来。假设为动态数组名为 $list$。

然后考虑 DP 的转移方式。

令 $f_{i,j}$ 是第 $i$ 行选取格子的状态是 $j$ 的时候，总共最多可以选取多少个格子。那么我们想一想什么时候可以从 $f_{i,j}$ 转移到第 $i+1$ 行的某个选取状态 $f_{i+1,k}$。

  1. 能继续向下转移的状态必然满足 $j$ 在一维动态数组数组 $list_i$ 里面。
  2. 保证格子不会在列上相邻，那么转移到的状态 $f_{i+1,k}$ 必然满足 $j\&k=0$
  3. $k$ 本身在第 $i+1$ 行是一个合法的选取方式所对应的状态。

这三个条件是一个递进的关系，我们可以来看一下示例代码：

for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < list[i].size; j++) { // 第1个条件
        int tmp = ((1 << (n - 1)) ^ j); // 第2个条件
        for (int k = tmp; k; k = (k - 1) & tmp) { // 还记得怎么快速枚举子集吗？
            if ((k & (k << 1)) == 0 && (k & zero[i + 1]) == 0) { // 第3个条件
                //转移
            }
        }
    }
}

满足这三个条件之后，我们就可以列出转移方程了：

$f_{i+1,k}=max(f_{i+1,k},f_{i,j}+num(k))$，这里 $num(k)$ 指的是状态 $k$ 所对应的集合里面的元素的个数。

最后我们来思考一下边界条件。很明显，我们需要首先考虑最上面一行的情况。

$f_{0,list[0][i]}=num(list[0][i])$

其余部分赋值为 $0$ 即可。

那么取出解我们自然是需要枚举所有的 $list[n - 1][i]$，取出 $f[n - 1][list[n - 1][i]]$ 的最大值。

当然，你可以使用 滚动数组 优化这道题的空间复杂度。

最近公共祖先

LCA

求 LCA 最容易想到的方案是：

代码如下，时间复杂度为 $\mathcal{O}(n)$。

int fa[MAX_N], vis[MAX_N];  // fa 数组保存每个结点的父节点，vis 数组用来标记
int LCA(int x, int y) {
    memset(vis, 0, sizeof vis);
    while (x != 0) {
        vis[x] = 1;
        x = fa[x];
    }
    while (vis[y] == 0) {
        y = fa[y];
    }
    return y;
}

标记所有的祖先似乎太浪费了，一种更好的想法是：先让 $x,y$ 走到同一深度，然后一起往上走，第一个相遇的位置就是它们的 LCA。

那么需要先通过 DFS 求出每个结点的深度，代码如下：

int d[MAX_N], fa[MAX_N];  // d 数组保存每个结点的深度
void dfs(int u) {
    d[u] = d[fa[u]] + 1;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v != fa[u]) {
            fa[v] = u;
            dfs(v);
        }
    }
}

int lca(int x, int y) {
    if (d[x] < d[y]) {
        swap(x, y);    // 让 x 为深度更深的那个点
    }
    while (d[x] > d[y]) {
        x = fa[x];  // 让 x 和 y 处于同一深度
    }
    while (x != y) {
        x = fa[x];
        y = fa[y];
    }
    return x;
}

但这种做法的时间复杂度依然为 $\mathcal{O}(n)$。

瓶颈在于通过fa数组往上走，每次走一步实在太慢了。那么有没有方法可以一次性走一大步呢？

答案是采用二进制的思想尝试往上跳，以下面这段代码为例：

while (d[x] > d[y]) {
  x = fa[x];  // 让 x 和 y 处于同一深度
}

可以改为：

int K = 0;
while ((1 << (K + 1)) <= d[x]) {
    K++;
}
for (int i = K; i >= 0; i--) {
    //如果 x 的 2^i 祖先深度大于等于 y 的深度，x 就往上跳到 2^i 祖先
}

其中 $K$ 为最大的整数满足 $2^{K}\le d[x]$。

我们让 $x$ 每次尝试跳 $2^i$ 步，$i$ 从 $K$ 开始从大到小枚举。如果跳跃后深度依然不小于 $y$，就选择跳跃。

换种角度思考，设 $t=d[x]-d[y]$，那么 $t$ 的二进制表示中 $1$ 的位置就是 $x$ 要跳的那步。相当于用若干个不同的 $2$ 的幂次来凑出这个 $t$，我们肯定会选择从大到小凑，并且最终方案肯定是唯一的。

同理，当 $x,y$ 到达同一深度后，两个点继续同时往上跳的步骤也可以用这种二进制尝试跳跃的方法。

如果能在 $\mathcal{O}(1)$ 时间内得到个结点的 $2$ 的幂次辈祖先，那么这种方法计算 $LCA(x,y)$ 的时间复杂度就为 $\mathcal{O}(\log n)$。

现在的问题变为如何预处理每个结点的 $2$ 的幂次辈祖先？

解决方法是采用动态规划，定义f[u][j]表示u结点 $2^j$ 辈祖先（如果不存在就为 $0$）。那么f[u][0]就是u结点的父亲结点，在 DFS 求深度的时候同时维护一下即可。

int f[MAX_N][20], d[MAX_N];
void dfs(int u) {
    d[u] = d[f[u][0]] + 1;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == f[u][0]) {
            continue;
        }
        f[v][0] = u;
        dfs(v);
    }
}

然后通过递推计算所有结点的 $2$ 的幂次辈祖先

for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i <= n; i++) {
        f[i][j] = f[f[i][j - 1]][j - 1];
    }
}

转移过程也很好理解，$i$ 的 $2^j$ 辈祖先等于 $i$ 的 $2^{j-1}$ 辈祖先的 $2^{j-1}$ 辈祖先。

这步预处理的时间是复杂度为 $\mathcal{O}(n\log n)$。

然后我们用刚才说的方法求 LCA：

int lca(int x, int y) {
    if (d[x] < d[y]) { // 让 x 是较深的点
        swap(x, y);
    }
    int K = 0;
    while ((1 << (K + 1)) <= d[x]) { // 找到不超过 x 深度的最大的 2 ^ k
        K++;
    }
    for (int j = K; j >= 0; j--) { // 尝试让 x 往上跳，跳到与 y 到同一高度
        if (d[f[x][j]] >= d[y]) {
            x = f[x][j];
        }
    }
    if (x == y) { // 如果这个时候两个点相等，那说明原来 y 是 x 的某个祖先，直接返回当前这个点就可以了
        return x;
    }
    for (int j = K; j >= 0; j--) { // 同时往上跳，跳到尽量高，但要求跳到的点还是不同的
        if (f[x][j] != f[y][j]) {
            x = f[x][j];
            y = f[y][j];
        }
    }
    return f[x][0]; // 最后 x 和 y 的父节点就是它们的 LCA 了
}

我们再回顾一下，首先通过交换确保x的深度更深，然后找到最大的 $K$ 满足 $2^K\le d[x]$，作为二进制尝试跳跃的上界。接着通过次若干次尝试往上跳，让x和y的深度相同。

这时候如果x和y已经是同一个结点了，就直接返回结果。否则，让两个点继续尝试同时往上跳一样的步数，注意只有在两个结点跳 $2^j$ 次步后 不相等 时才会往上跳。换句话说，循环结束后，x和y分别是它们 LCA 的儿子。因此它们的父节点就是 LCA。

刚才我们所说的算法就是倍增法。这样，我们就使用了 倍增法 解决 LCA 问题，预处理时间复杂度 $\mathcal{O}(n \log n)$，单次查询的时间复杂度为 $\mathcal{O}(\log n)$。

LCA 的应用（一）

接下来我们看一个 LCA 的经典应用，求树上两个点的距离。

我们常用的做法是，首先任意选取一个点为根结点。由于是求树上的最短路径，实际上就对应树上的简单路径。假设 $u, v$ 的最近公共祖先为 $lca$，我们可以把 $u, v$ 之间的路径拆成两部分，$u$ 到 $lca$ 的路径加上 $v$ 到 $lca$ 的路径。

这样，我们只需要在 DFS 的同时用 $dis_i$ 记录结点 $i$ 到根结点的距离。那么

\[\displaystyle len(u, v) = dis[u] + dis[v] - 2\times dis[lca]\]

LCA 的应用（二）

给定一棵带有边权的树，之前我们讲过如何求树上一条路径 $x\rightarrow y$ 的长度，用的方法是记录每个结点到根的距离，然后路径长度为：

\[\displaystyle dis[x]+dis[y]-2\times dis[LCA]\]

如果现在问题变为求树上一条路径的最大（最小）呢？显然不能再用上述的方法了，因为加法的逆运算是减法，而 max 和 min 运算无法求逆。

下面通过路径倍增求一条路径上边权的最大值。

还记得f数组吗？f[u][j]表示u结点 $2^j$ 辈祖先，现在需要再维护一个数组g，g[u][j]表示u到f[u][j]这条链上边权的最大值。

初始的时候，g[u][0]为u结点上面那条边的权值，dfs函数修改为：

int f[MAX_N][20], g[MAX_N][20], d[MAX_N];
void dfs(int u) {
    d[u] = d[f[u][0]] + 1;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == f[u][0]) continue;
        f[v][0] = u;
        g[v][0] = e[i].w;
        dfs(v);
    }
}

然后通过动态规划来计算，转移方程也很显然，就是把从i到f[i][j]这条链，拆成i到f[i][j-1]和f[i][j-1]到f[i][j]两条链，然后取最大值。

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

那么求 $x\rightarrow y$ 这条路径上边权的最大值，也就是求这两个结点到它们 LCA 的这两条链上边权的最大值。

其实只是在求 LCA 的基础上多维护了一个最值。

int cal(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    int K = 0;
    while ((1 << (K + 1)) <= d[x]) K++;
    int res = 0;
    for (int i = K; i >= 0; i--) {
        if (d[f[x][i]] >= d[y]) {
            res = max(res, g[x][i]);
            x = f[x][i];
        }
    }
    if (x != y) {
        for (int i = K; i >= 0; i--) {
            if (f[x][i] != f[y][i]) {
                res = max(res, max(g[x][i], g[y][i]));
                x = f[x][i];
                y = f[y][i];
            }
        }
        res = max(res, max(g[x][0], g[y][0]));
    }
    return res;
}

离散化与散列表

离散

我们将学习离散化和一些应用。那么在将离散化的方法之前，先给大家看两张图。

第一张图是一个函数图像，第二张图是一个点阵。那么它们呈现一种怎样的特点呢？

第一张图我们可以看到一条曲线，那么曲线上的某个点 $(x,y)$ 代表着 $y=arccot(x)$。然后再看看第二张图。图的点就不一样了，我们可以看到它们是独立地出现在了整个圆里面的某个位置，而且还有颜色。

左边的函数图像，我们称函数 $y=arccot(x)$ 在图像上所表示的区间里面是 连续的。而里面讲到的 离散，其实代表的就是 不连续。

我们的生活和计算机的实际应用中也可以举出很多和离散有关的例子：

  1. 你所在的班级里面，每一个人的名字，我们可以把这些名字都取出来，放在一个线性表里面，这些数据都是离散的。
  2. 在计算机里面我们所看到的图片，实际上也是离散的。计算机里的图片就是离散的二进制比特流。图像（灰度图像）像素的灰度值在计算机里是从 $0$ 到 $255$（实际上是用二进制表示的），即 $0,1,2,3\cdots255$，$0$ 代表黑色，$255$ 代表白色，只有 $0$ 到 $255$ 的整数，没有其他整数，而且没有两个整数之间的小数，即不连续的，这就叫离散。这也是为什么如果你把一个图片放得太大了，会变得非常模糊。

离散化

离散的数据是混乱无序的，没有规律的，我们很难去直接对这些数据进行整体的操作。而且它们的范围可能很大，我们甚至连存储它们都会变得非常困难，因为我们需要一个很大的容器去分辨这些数据。

所以我们在处理这些规模和范围极其庞大的数据的时候，需要对数据进行 离散化 的操作。离散化的基本思想，其实就是在范围庞大的数据当中，去选择对题目的解决有意义的那么一部分，将它们重新编号，然后再进行处理。

原数据 1 5 12 19 23 108
离散化后的数据 1 2 3 4 5 6

比如说有这样一个题目：

有 $n$ 个人，第 $i$ 个人会在第 $a_i$ 分钟开始的时候进入房间，在第 $b_i$ 分钟结束的时候离开房间，房间里面人最多的时候会有多少个人？房间里面 人最多 这个状态的持续时间是多久？

$n\le 1000,1\le a_i\le b_i\le 10^{18}$。

最简单粗暴的方式，我们开一个数组 $num$，$num_j$ 表示第 $j$ 分钟房间里面有多少人。然后对于第 $i$ 个人，将 $num$ 的 第 ${a_i}$ 到 ${b_i}$ 个元素都加上 $1$，最后进行统计和计算。

$1\le a_i\le b_i\le 10^{18}$，数据范围太大了，我们甚至存储不了每分钟房间里面有多少人这个关键信息。

但是我们再来思考一个问题，某一分钟开始的时候，只有在有人员进出的时候，房间的人数才会 产生变化。那么，对于每一个人而言，他只会进出房间各一次。所以，人员进出这个事件的出现次数，最多为 $2\times n$。换句话来讲，也就是所有的 $a_i$ 和 $b_i+1$，不同的数最多有 $2\times n$ 个。

那么我们就可以这么做：将所有的 $a_i$ 和 $b_i+1$ 组成一个按照元素从小到大排列成的集合 $S={S_1,S_2,\cdots,S_t}$。后续的处理，我们用 $i$ 代替 $S_i$，代表着在第 $i$ 个时间点发生了 人员增加 或者 人员减少 的事件。这里我们可以构造一组样例：

$i$ $a_i$ $b_i$ $b_{i+1}$
$1$ $1$ $3$ $4$
$2$ $4$ $8$ $9$
$3$ $7$ $9$ $10$
$4$ $3$ $6$ $7$

可以构造出集合 $S={1,3,4,7,9,10}$。我们将每个 $S_i$ 替换成 $i$：

$i$ $a_i$ $b_i+1$
$1$ $1$ $3$
$2$ $3$ $6$
$3$ $4$ $5$
$4$ $2$ $4$

可以得到下面这张表：

时间点（$i$）/人员编号 $1$ $2$ $3$ $4$ $num_i$
$0$ $0$ $0$ $0$ $0$ $0$
$1$ $1$ $0$ $0$ $0$ $1$
$2$ $1$ $0$ $0$ $1$ $2$
$3$ $0$ $1$ $0$ $1$ $2$
$4$ $0$ $1$ $1$ $0$ $2$
$5$ $0$ $1$ $0$ $0$ $1$

我们可以在所有的 $num$ 里面找到最大值为 $2$，代表房间内最多同时有 $2$ 人。

至于计算状态的持续时间，如果第 $i$ 个时间点开始的时候房间的人员变为最多，那么我们就用 $S_{i+1}-S_{i}$ 统计就可以了。

$num_2=num_3=num_4=2$，所以持续的时间是 $S_5-S_2=6$ 分钟。

有些数据本身很大，自身无法作为数组的下标保存对应的属性。如果我们想要妥善地保存它们并且可以进行计算，就需要对它们 重新标号，并且建立起 一对一 的 映射关系。

在现实生活中有很多这种例子。一个学校的学生很多，于是学校给每个学生一个 学号 作为这个学生的标识，用于和其他学生进行区别。

离散化并不是一个单独的算法，一般而言，这个算法都是对数据的预处理，用于缩小数据的范围，然后使用其他的算法去处理问题。

来思考一个问题：一个排好序的序列 $S$，怎么快速实现离散化？

其实很简单，我们发现如果 $S_i\ne S_{i-1}$，就说明 $S_i$ 没有在之前序列里面出现过，那么 $S_i$ 就应该是离散化之后的序列的一个元素。我们可以这么实现：

int len = 0;
for (int i = 1; i <= n; i++) {
    if (S[i] != S[i - 1]) {
        S[++len] = S[i];
    }
}

那么 $S_1,S_2,\cdots,S_{len}$ 就会是离散化之后的新序列，而 $S_{len+1},S_{len+2},\cdots,S_n$ 则保持原来的值不变。

在 C++ 的 algorithm 库里面有一个函数叫 unique，我们可以这么做，实现上面的代码类似的功能：

unique(S + 1, S + n + 1);

当然，如果你需要真的把重复的元素删掉，就需要使用 动态数组 了：

vector<int>::iterator new_end = unique(S.begin(), S.end()); //注意 unique 函数的返回值，是一个迭代器（指针）
S.erase(new_end, S.end());

所以建议使用 动态数组 来实现离散化。因为你也可以立刻得到离散化后的序列长度。

前缀和与差分

前缀和回顾

首先回顾一下前缀和。我们知道前缀和优化可以用于解决一些求连续子段相关信息的问题。

我们对数列 $a_1,a_2,\cdots,a_n$ 进行处理，令 $sum_i = a_1+a_2+\cdots+a_i$，那么求数列第 $i$ 到数列第 $j$ 项的和就可以使用 $sum_j-sum_{i-1}$ 去计算了。

前缀和优化还有一些变种，我们可以用类似的方式去求前缀最大值或者最小值。我们也可以使用后缀代替前缀去进行相应的计算，等等。

差分回顾

我们既然可以将序列 $a_1,a_2,\cdots,a_n$ 生成一个前缀和序列 $sum_1,sum_2,\cdots,sum_n$，那么反过来，我们是不是也能在序列 $sum_1,sum_2,\cdots,sum_n$ 的基础上生成序列 $a_1,a_2,\cdots,a_n$ 呢？

肯定是可以的。我们知道 $sum_i=a_1+a_2+\cdots+a_i$，那么 $a_i=sum_i-sum_{i-1}$。于是我们便可以按照这个思路去构造一个序列的差分序列。

令原序列为 $S={S_1,S_2,\cdots,S_n}$，那么我们可以构造一个差分序列 $T={S_1-S_0,S_2-S_1,\cdots,S_n-S_{n-1}}$（默认 $S_0$ 为 $0$）

我们回到这个问题：

有 $n$ 个人，第 $i$ 个人会在第 $a_i$ 分钟开始的时候进入房间，在第 $b_i$ 分钟结束的时候离开房间，房间里面人最多的时候会有多少个人？房间里面 人最多 这个状态的持续时间是多久？

我们之前用表格记录下来了每个人出现在房间里面的时间段。可以看到的是，每个人出现在房间里面的时间段是连续且唯一的。

结合到差分，实际上我们可以想到的是，记录下每个时间段开始的时候，进入房间 和 离开房间 的人数。这样我们就可以在总体上得到每个时间段的人数相对于上一个时间段的变化。

$i$ $a_i$ $b_{i+1}$
$1$ $1$ $3$
$2$ $3$ $6$
$3$ $4$ $5$
$4$ $2$ $4$

可以得到：

$num_1 = num_0 + 1 - 0 = 1$

$num_2 = num_1 + 1 - 0 = 2$

$\cdots$

$num_6 = num_5 + 0 - 1 = 0$

剩下的部分可以考虑自己试着写一写。

总结：

步骤一：统计每个时刻进入房间和离开房间的人数：

sum[x]++; // 在 x 时刻有一个人进入房间
sum[x]--; // 在 x 时刻有一个人离开房间

步骤二：对 $sum[\ ]$ 数组求前缀和，就可以求出每个时刻的人数。

sum[i] = sum[i - 1] + sum[i]; // 其中 sum[i - 1] 为上一页公式中的 num[i-1]，sum[i] 为每行后面两个数的和

实际上程序的空间和时间大小和时刻的最大值有关，所以当时刻的最大值很大时，还是需要离散化的，将维护的区间缩小。

散列表

我们刚刚学习了离散化。

在处理规模和范围极其庞大的数据的时候，我们会对数据进行 离散化 的操作，在这范围庞大的数据当中，去选择对题目的解决有意义那一部分，将它们重新编号，然后再进行处理。

重新编号的时候，我们会先把这些数据按照某个顺序排个序，然后按照排序的结果挨个编号，结果一定是连续的。

总的来讲，如果这时只是需要这堆数据的 相对属性，那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

但是有时候我们会遇到这样的问题：

对于第一种情况，你用离散化也是没问题的，只不过排序这一步显得有些多余。但是对于第二种情况，无论如何你也不能采取离散化的操作了，因为元素的动态添加和删除会对离散化之后形成的映射表产生破坏。

那怎么办呢？这里我们来学习一种新的数据结构——散列表。散列表也叫 哈希表。下面是一个例子。

我们可以看到在这个散列表里面，每一个拼音都有了一个对应的值。比如说a对应 $1$，an对应 $4$。

那么其实我们也可以让a对应 $4$，an对应 $1$，在散列表里面，这两种映射方式在本质上没有任何区别。我们只需要保证，一个关键字只对应一个值，而一个值只对应一个关键字，这个和离散化是一样的（即 一对一 的映射）。

看到这里，实际上我们还可以得到散列表的另一个优点，那就是对于同一个散列表，我们只需要某个关键字本身，就可以根据这个关键字去计算出它在散列表里面对应的值，而不需要像离散化那样要把所有的数据 统筹起来 思考。

基础数论

快速幂

先给你一个很简单的问题，你需要求：

\[\displaystyle x^y \% (10^9+7)\]

的值。

很明显，当 $y$ 不大的时候，你只需要写一个循环求就行。

那如果 $y\le 10^{18}$ 呢？很明显你不能再这么做了。

这时候我们可以得到这么一个结论：

  1. 当 $y$ 是偶数的时候，有 $x^y=x^{y/2}\times x^{y/2}$。
  2. 当 $y$ 是奇数的时候，有 $x^y=x^{y/2}\times x^{y/2}\times x$。

所以，如果我们求出来了 $x^{y/2}$ 的值，就可以在 $O(1)$ 的复杂度内求出 $x^y$ 的值。而对于 $x^{y/2}$ 亦同理，只要求出来了 $x^{y/4}$ 的值，就可以在 $O(1)$ 的复杂度内求出 $x^{y/2}$ 的值。

循环往复，直到推进到需要求 $x^0$ 的值，而 $x^0=1$。

接下来我们来看一份示例代码：

long long power(long long x, long long y) {
    if (y == 0) { //任何数的 0 次方都是 1
        return 1;
    }
    long long k = power(x, y >> 1); //先求出 x^(y/2) 的结果
    k = k * k % mod;
    if (y & 1) { //y 是奇数的时候，需要额外乘以 x
        k = k * x % mod;
    }
    return k;
}

那么现在我们对问题进行进一步修改：

你需要求：

\[\displaystyle x^y \% (10^{12}+7)\]

的值。

我们回到刚才的实现。

k = k * k % mod;

$k$ 无论如何是不会大于 $mod$ 的。但是当 $mod$ 取到 $10^{12}+7$ 的时候，$k \times k$ 会超出 long long 可以承受的范围。

实际上你可以模仿乘法快速幂去写一个快速加法去求 $x\times y \% mod$ 的值：

long long mul(long long x, long long y) {
    if (y == 0) {
        return 0;
    }
    long long k = mul(x, y >> 1);
    k = (k + k) % mod;
    if (y & 1) {
        k = (k + x) % mod;
    }
    return k;
}

小 tips

$10^9+7$ 是一个很有意思的值。它符合以下几个特点：

  1. 是质数。
  2. $2\times(10^9+7)$ 不会超出 int 的范围。
  3. $(10^9+7)^2$ 不会超出 long long 的范围。

所以绝大部分的题目取余的时候都会用这个数，但是还是 注意读题，因为有些有 恶趣味 的出题人会利用这一点卡掉一些在这方面出现了思维定势而不认真读题的选手。

实际上还有一个很有用的数叫 $998244353$。当然现在你不需要关心这个数到底有什么用。只是这两个数你会在数论等问题中会经常看见，不必感到奇怪。

埃氏筛法

之前我们已经学习过怎么求单个数是否是质数。但实际上在大部分的数论问题里面，我们都会需要在很短的时间内处理大量的数据，那么之前的算法其实就不够用了。

这里将介绍两种算法，一种是埃氏筛法，接下来还有欧拉筛法，这两种筛法在不同的场合中有其独特的作用和意义。

我们考虑质数的定义：一个数当只有自身和 $1$ 两个约数的时候为质数。

所以对 $1\sim n$ 这 $n$ 个数筛选其中的质数，我们可以从 $2$ 到 $n-1$ 的每一个数：去枚举它的 $2,3,\cdots$ 倍，只要这个倍数还在 $1\sim n$ 的范围内，我们就标记上。否则就停下来去计算枚举下一个数的倍数。以下是示例代码：

for (i = 2; i < n; i++) {
    for (j = i * 2; j <= n; j += i) {
        prime[j] = false; //prime 为 false 代表是偶数。
    }
}

我们来看一看上面这个操作的时间复杂度：

我们需要先求出时间频度，然后转换为时间复杂度。

$T(n)=n\times(\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots\frac{1}{n-1})$

我们令 $f_i=\frac{1}{2^{i-1}+1}+\frac{1}{2^{i-1}+2}+\cdots+\frac{1}{2^i}$

那么 $f_i<\frac{1}{2^{i-1}}+\frac{1}{2^{i-1}}+\cdots+\frac{1}{2^{i-1}}$（总共 $2^{i-1}$ 项），所以 $f_i<1$。

而 $\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\cdots\frac{1}{n-1}\le f_1+f_2+\cdots+f_{\lceil log_2(n)\rceil}< log_2(n)$

所以 $T(n) < nlog_2(n)$。那么上述操作的时间复杂度是 $O(nlogn)$ 的。

我们来思考一下，刚才的操作，除了筛选质数以外我们还做了什么呢？

与此同时我们找到了 $1\sim n$ 的每一个数除了自身和 $1$ 之外的其他所有约数具体的值。因为对于每一个数，当循环进行到 $i$ 为它的约数时，在内层循环中它都会被扫描到。

所以我们也可以得到这样一个结论：$1\sim n$ 的所有数的约数个数之和约为 $nlog_2(n)$。这个结论在你以后处理一些枚举问题的时候会给你很大的帮助。

实际上对于刚才的埃氏筛法，如果你只是为了找质数的话，还可以进行一些优化。那么在这里我们首先将讲一下这些优化。

我们回顾一下刚才的代码：

for (i = 2; i < n; i++) {
    for (j = i * 2; j <= n; j += i) {
        prime[j] = false; //prime 为 false 代表是偶数。
    }
}

实际上有两处可以明显优化的地方：

  1. 对于 $i$ 是合数的情况，内层循环很明显是不用执行的，因为 $i$ 的倍数肯定都被标记过了。
  2. 对于 $j/i < i$ 的情况，那些 $j$ 肯定也被标记过了。

于是我们可以由此进行优化并且把代码改成这样：

for (i = 2; i < n; i++) {
    if (prime[i] == false) {
        continue;
    }
    // 这里你可以把所有的质数记录下来
    for (j = i * i; j <= n; j += i) {
        prime[j] = false; //prime 为 false 代表是合数。
    }
}

优化后的时间复杂度是 $O(nloglogn)$，这里就不再证明了，一方面证明比较复杂，另一方面如果只是区间预处理质数在这里我们会一起学习时间复杂度更优的算法。

欧拉筛法

接下来我们用另外一种算法（欧拉筛法）去预处理 $1\sim n$ 中所有的质数。

我们直接看代码：

for (int i = 2; i <= n; i++) {
    if (prime[i] == true) {
        list[++list[0]] = i;
    }
    for (int j = 1; j <= list[0]; j++) {
        if (i * list[j] > n) {
            break;
        }
        prime[i * list[j]] = false;
        if (i % list[j] == 0) {
            break;
        }
    }
}

$list$ 是我们记录下来的质数表。$list_0$ 实时记录着质数表的大小。

学会阅读这段代码，其他地方你肯定能很好的理解，但是这段代码：

if (i % list[j] == 0) {
    break;
}

可能你就反应不过来了。这实际上是欧拉筛中最为重要的语句。正是这条语句保证了欧拉筛的时间复杂度实际上是 $O(n)$ 的。

我们试着分析一下为什么刚才讲的埃氏筛法为什么无论怎么优化都优化不到 $O(n)$。我们举一个例子，在优化后的埃氏算法中，$prime_{30}$ 的值会在 $i=2$ 和 $i=3$ 中被访问。

对于一个有多个不同的质因数的数而言，它可能会被访问多次。而这正是需要得到优化的地方。我们知道一个合数最小的质因数一定是确定的，那么我们如果保证一个合数只会被它最小的质因数访问到就万事大吉了。

我们令一个合数 $x={a_1}^{p_1}\times b$。（$a_1<b$ 的所有质因数（如果 $b$ 不是 $1$），$a_1$ 为质数）：

在循环中 $i=x/a_1,list_j=a_1$ 的时候，$x$ 会被标记。但是当 $i$ 是 $x$ 除以其他质因数的商的时候，在 $j=a_1$ 的时候会直接 退出内层循环（因为这个时候的 $i$ 一定是 $a_1$ 的倍数）。所以我们可以得到任意合数 $x$ 只会被对应的 $a_1$ 标记一次。

既然每个合数都只会被标记一次，那么整个算法的复杂度便被成功地优化为了 $O(n)$。

接下来我们会讲欧拉筛的其他用处。

欧拉函数

对于 $1\sim n$ 中与 $n$ 互质的数的个数，我们称其为 $n$ 的 欧拉函数 的值。

我们令 $n$ 的 欧拉函数 的值是 $f_n$，然后看一下如何推出 $f_n$ 的值。

我们对 $n$ 做质因数分解：

\[\displaystyle n={a_1}^{p_1}\times {a_2}^{p_2}\times \cdots \times {a_k}^{p_k}\]

因为 $a_1,a_2,\cdots,a_k$ 都互质，所以有：

  1. $n$ 个数中是 $a_1$ 的倍数的数占了总数的 $\frac{1}{a_1}$。然后去除掉 $a_1$ 的倍数。
  2. 剩下的数中是 $a_2$ 的倍数的占了总数的 $\frac{1}{a_2}$。然后去除掉 $a_2$ 的倍数。
  3. $\cdots$

那么当我们一步一步地把这些数都剔除干净之后，剩下的数的个数是 $n\times \frac{a_1-1}{a_1}\times \frac{a_2-1}{a_2}\times\cdots\times \frac{a_k-1}{a_k}$。这就是欧拉函数的公式。

费马小定理和欧拉定理

接下来我们来看一些和欧拉函数相关的定理。

费马小定理

如果 $p$ 是一个质数，而整数 $a$ 不是 $p$ 的倍数，则有 $a^{p-1}\equiv 1\bmod p$。

我们来看看这个定理的证明。

引理 1

若 $a,b,c$ 为任意三个整数，且 $gcd(p,c) = 1$，那么当 $ac \equiv bc(mod\ p)$ 的时候，有 $a \equiv b(mod\ p)$。

这个比较简单，我们使用之前学习过的模运算的性质就行。

$ac \equiv bc(mod\ p)$，那么 $(a-b)c\equiv 0(mod\ p)$。

由于 $c,p$ 互质，所以同余号左边的 $c$ 是可以直接约去的，于是就得到 $a,b$ 关于 $p$ 同余。

定理证明

令集合 $S$ 为 $1\sim p-1$ 这 $p-1$ 个整数组成的集合。

\[\displaystyle S= \{1,2,\cdots,p-1\}\]

我们对集合 $S$ 进行操作。令 $p$ 为 质数，然后将该集合里面的所有元素乘上一个不为 $p$ 的倍数的整数 $a$，得到下面这个集合：

\[\displaystyle T=\{a,2a,\cdots,(p-1)a\}\]

现在我们来证明下面两个结论：

由此，将 $S$ 和 $T$ 这两个集合里面的元素分别全部相乘，得到的结果对 $p$ 是同余的。于是我们可以得到下面这个等式：

\[\displaystyle (p-1)!\equiv a^{p-1}(p-1)!(mod\ p)\]

由于 $(p-1)!$ 和 $p$ 互质，所以可以把同余号两边的 $(p-1)!$ 直接约去，得到：

\[\displaystyle a^{p-1}\equiv 1(mod\ p)\]

是不是很熟悉？这就是费马小定理的表达式。证明过程到这里也就结束了。

欧拉定理

欧拉定理有很多个，这里我们谈及的是 数论 的欧拉定理，它的内容是：

如果 $a,p$ 互质，则有 $a^{\phi (p)}\equiv 1\bmod p$，其中 $\phi (p)$ 是 $p$ 的欧拉函数的值。实际上，费马小定理是欧拉定理中，$p$ 为质数的特殊情况。

基础组合数学

排列数

从 $n$ 个不同元素中任取 $m(m \le n)$ 个元素，按照一定的顺序排成一列，叫做从 $n$ 个不同元素取出$m$个元素的一个排列。能够组成的不同排列总数记作 $A^m_n$ .

当 $n=m$ 时，称作 $n$ 的全排列。

其中，第 $1$ 个位置可以在 $n$ 个数中任选，第 $2$ 个位置可以在剩下的 $n-1$ 个数中任选，第 $i$ 个数可以在 $n-i+1$ 个数中任选，因此排列的计算公式如下：

\[\displaystyle A_n^m=n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}\]

例题 1

将字母表中的 $26$ 个字母排成一行，使得元音字母a、e、i、o、u中任意两个都不能连续出现，这样的方案数有多少？

解析

先排列 $21$ 个辅音字母，共有 $A_{21}^{21}$ 种排列方法。然后把元音字母进行插空，来保证不相邻，有 $A_{22}^5$ 种方案数，根据乘法原理，总方案数为 $A_{21}^{21}\times A_{22}^5$ 种。

例题 2

用 $1 \sim 9$ 组成一个四位数，满足所有数互不相同，且 $1$ 与 $2$ 不能相邻，求合法的数字个数。

解析

$1 \sim 9$ 共能组成 $A^4_9$ 个互不相同的四位数，再减去 $1$ 与 $2$ 相邻的四位数就是答案。

$1$ 和 $2$ 相邻的排列共有 $A_2^2 $ 种，在四位数中共有 $3$ 种放置方法。剩下的 $2$ 个数放置方案共有 $A_7^2$ 种，所以共有 $3 \cdot A_2^2\cdot A_7^2$ 种排列。

所以答案为 $A^4_9-3 \cdot A_2^2\cdot A_7^2=2772$ 种。

圆排列

有一组元素，将其排成一个圆，这种排列叫做圆排列。

在圆排列中，12345和23451是同一种排列。对于一个圆排列，从不同位置断开，就能组成不同的线性排列，对于一个元素个数为 $r$ 的圆排列，它在线性排列中被重复计算了 $r$ 次。

因此对于圆排列 $Q_n^r$ ，有

\[\displaystyle Q_n^r=\frac{A_n^r}{r}\]

特别的，对于圆的全排列，有

\[\displaystyle Q_n^n=\frac{A_n^n}{n}= (n-1)!\]

例题

甲，乙，丙，丁，戊 $5$ 人要围成一圈，其中甲乙必须相邻，问有多少种合法的排列方案。

解析

甲乙视作一个整体，他们相邻的排列有 $A_2^2$ 种，再将他们与其他三人一起计算圆排列，有 $Q_4^4$ 种方案。总方案数为 $A_2^2 \cdot Q_4^4=12$ 种。

错位排列

$n$ 封不同的信，编号分别为 $1,2,3,\cdots,n$ ，现在要把这 $n$ 封信放到编号为 $1,2,3,\cdots,n$ 的信封中，要求信的编号与信封的编号不能相同，有多少种不同的放置方法。

考虑递推。假设我们当前在处于第 $n$ 封信，初始时先将第 $n$ 封信放在第 $n$ 个信封。对于前 $n-1$ 封信，有两种递推情况：

对于第一种情况，由于前 $n-1$ 个信封已经装错，可以将其中任意一个与 $n$ 调换位置，共有 $f(n-1) \times (n-1)$ 种方案。

对于第二种情况，我们把唯一一个没有装错的位置的信与 $n$ 交换，即可得到一个错排情况。共有 $(n-1) \times f(n-2)$ 种情况。

对于其他情况，无法通过一次操作把序列变成一个错排。

所以可以得到错位排列的递推式为

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

组合数

从 $n$ 个不同元素中，任取 $m(m \le n)$ 个元素组成一个集合。叫做从 $n$ 个不同元素取出 $m$ 个元素的一个组合。能够组成的不同组合总数记作 $C^m_n$，也常用 $\binom{n}{m}$ 表示。

此时我们已经知道取出 $m$ 个数的排列数为 $A_n^m$ ，其中每个组合在排列中被重复计算了 $m!$ 次，因此组合数的计算公式如下：

\[\displaystyle C_n^m=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!}\]

性质 1

$C_n^k=C_n^{n-k}$

相当于对原集合在全集中取补集，方案数不变。

性质 2

$\frac{k}{n}C_n^k=C_{n-1}^{k-1}$

$n$ 个元素里取 $k$ 个元素有 $C_n^k$ 种，其中包含第一个元素的方案有 $\frac{k}{n}C_n^k$ 种。

而在剩下的 $n-1$ 个元素里取 $k-1$ 个元素有 $C_{n-1}^{k-1}$ 种。因此等式成立。

性质 3

范德蒙（Vandermonde）卷积公式：

\[\displaystyle C_{m+n}^{r}=\displaystyle\sum_{k=0}^rC_{m}^{k}C_{n}^{r-k}\]

把 $n+m$ 个元素划分成两个子集 $A,B$，每个子集分别有 $m$ 和 $n$ 个元素，每次在 $m$ 个中取 $k$ 个，在 $n$ 个中取 $r-k$ 个，就可以组成在 $n+m$ 个元素中取 $r$ 个的合法方案。

当 $n=m$ 时，有\(\displaystyle \sum\limits_{k=0}^{n}(C_n^k)^2=C_{2n}^n\)

杨辉三角（帕斯卡恒等式）

从 $n$ 个元素中取 $k$ 个元素。对于某个元素 $X$ ，有取或不取两种可能性。当取这个元素时，需要在剩下的 $n-1$ 个元素中取 $k-1$ 个元素；当不取这个元素时，需要在剩下的 $n-1$ 个元素中取 $k$ 个元素，可以得到等式：

\[C_{n}^k = C_{n-1}^{k-1} + C_{n-1}^k\]

通过这一恒等式，我们可以实现 组合数的递推。

多重集合的排列与组合

多重集的排列数

多重集是指包含重复元素的广义集合。设 $S={n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,}$ 表示由 $n_1$ 个 $a_1$ ， $n_2$ 个 $a_2$ ，…， $n_k$ 个 $a_k$ 组成的多重集， $S$ 的全排列个数为

\[\displaystyle \frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}\]

具体地，你可以认为你有 $k$ 种不一样的球，每种球的个数分别是 $n_1,n_2,\cdots,n_k$ ，且 $n=n_1+n_2+\ldots+n_k$ 。这 $n$ 个球的全排列数就是多重集的排列数。

例题 1

用 $1,2,2,3,3,3,4,4,4,4$ 这十个数字能组成多少个不同的十位数？

解析

因为没有 $0$，所以答案就是多重集的全排列个数： $\frac{n!}{\prod_{i=1}^kn_i!}=\frac{10!}{4!3!2!1!}=12600$ 种。

例题 2

多重集合 $S=\lbrace 3\cdot a,2 \cdot b,4 \cdot c\rbrace$，求 $S$ 的 $8$ 排列个数。

解析

多重集合的非全排列个数没有直接的公式，但某些情况下还是能够求解的，这里采用分类讨论的方法。

一共 $9$ 个元素，$8$ 排列是少用了一个元素，那么可以分成三种独立的情况：

所以 $S$ 的 $8$ 排列个数为 $420+280+560=1260$。

多重集的组合数

多重集合的组合有以下定理：

设 $S=\lbrace n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\rbrace$ 为多重集合，若 $r\le n_i,i=1,2,\cdots,k$，那么 $S$ 的 $r$ 组合数是 $C_{k+r-1}^r$。

证明：

$S$ 的 $r$ 组合是 $S$ 的一个子集，也是一个多重集合 $\lbrace x_1\cdot a_1,x_2\cdot a_2,\cdots,x_k\cdot a_k\rbrace$，其中满足 $x_1+x_2+\cdots+x_k=r$，$x_i$ 都为非负整数。

那么组合数的个数就等于这个不定方程解的个数，即每一个组合和每一个解是一一对应的。

可以用隔板法解决，现在有 $r$ 个元素，用 $k-1$ 个隔板把他们分成 $k$ 个部分，每个部分允许为空，那么答案就是 $C_{k+r-1}^{k-1}=C_{k+r-1}^r$。

例题 1

不定方程 $x_1+x_2+x_3+x_4=6$ 的非负整数解的个数有多少个？

解析

使用隔板法求解，现在有 $6$ 个元素，用 $3$ 个隔板把他们分成 $4$ 个部分，每个部分允许为空，答案为 $C_9^3$。

例题 2

把 $2n$ 个人分成 $n$ 组，每组 $2$ 人，求不同的分组方法数。

如 $n=2$，有三种分法：

解析

先选 $2$ 个加入到第一组，有 $C_{2n}^2$ 种方法。

再选 $2$ 个加入到第二组，有 $C_{2n-2}^2$ 种方法。

再选 $2$ 个加入到第三组，有 $C_{2n-4}^2$ 种方法。

$\cdots\quad\cdots$

最后的 $2$ 个人加入到第 $n$ 组，有 $C_{2}^2$ 种方法。

$n!$ 个有区别的方案对应着一个无区别的方案，所以最终答案为

\[\displaystyle \begin{aligned} &\quad\frac{1}{n!}C_{2n}^2C_{2n-2}^2\cdots C_{2}^2\\ &=\frac{1}{n!}\frac{(2n)!}{(2n-2)!2!}\frac{(2n-2)!}{(2n-4)!2!}\cdots\frac{2!}{0!2!}\\ &=\frac{(2n)!}{n!2^n} \end{aligned}\]

更一般的情况，我们有如下定理：

把 $n$ 个不同的元素划分成 $k$ 个不同的组，使得第 $i$ 个组有 $n_i$ 个元素，并且满足 $n=n_1+n_2+\cdots+n_k$。那么这样的划分方案数等于 $\frac{n!}{n_1!n_2!\cdots n_k!}$。

如果组之间没有区别，且 $n_1=n_2=\cdots=n_k$，那么划分方案数为 $\frac{n!}{k!n_1!n_2!\cdots n_k!}$。

二项式定理

设 $n$ 为正整数，对于任何 $x,y$ ，有:

\[\displaystyle (x+y)^n=\sum_{i=0}^n\binom{n}{i}x^{i}y^{n-i}\]

证明

\[\displaystyle (x+y)^n=(x_1+y_1)\cdot (x_2+y_2)\cdot(x_3+y_3)...(x_n+y_n)\]

其中 $x_1=x_2=…=x_n=x,y_1=y_2=…=y_n=y$

那么对于 $x^ky^{n-k}$ ，相当于在 $x_1,x_2,…,x_n$ 中选取 $k$ 个令 $x$ 作为乘积，而在剩下的 $n-k$ 个中选取 $y$ 作为乘积，共有 $C_n^k$ 种取法，所以 $x^ky^{n-k}$ 的系数为 $C_n^k$。

推论 1

\[\displaystyle C_n^0+C_n^1+C_n^2+...+C_n^{n-1}+C_n^{n}=2^n\]
证明

对于

\[\displaystyle (x+y)^n=\sum_{i=0}^nC_n^ix^{i}y^{n-i}\]

令 $x=y=1$ ，有

\[\displaystyle (1+1)^n=\sum_{i=0}^nC_n^i\]

即

\[\displaystyle 2^n=C_n^0+C_n^1+C_n^2+...+C_n^{n-1}+C_n^{n}\]

证毕。

推论2

\[\displaystyle C_n^0+C_n^2+\cdots=C_n^1+C_n^3+\cdots=2^{n-1}\]
证明

对于

\[\displaystyle (x+y)^n=\sum_{i=0}^nC_n^ix^{i}y^{n-i}\]

令 $x=1,y=-1$ ,有\(\displaystyle 0=\displaystyle\sum_{k=0}^{n}(-1)^kC_n^k\)

把上式移项，可以得到：\(\displaystyle C_n^0+C_n^2+\cdots=C_n^1+C_n^3+\cdots=2^{n-1}\)

证毕。

鸽巢原理

鸽巢原理又称为抽屉原理。其最简单的形式如下：

如果 $n + 1$ 个物体被放进 $n$ 个盒子，那么至少有一个盒子包含两个或者两个以上的物体。

可以用反证法来证明： 如果这 $n$ 个盒子中每个都至多含有一个物体，那么物体的总数最多是 $n$，和已知的有 $n + 1$ 个物体矛盾，故某个盒子必然包含两个及以上的物体。

例题 1

已知 $n+1$ 个不同的正整数，它们全都小于或等于 $2n$ ，证明当中一定有两个数是互质的。

证明

首先我们需要利用一个特性：两个相邻整数一定互质。

在这个基础上，我们构造 $n$ 个鸽巢。对于第 $i$ 个鸽巢，我们放入 $2i-1,2i$ 两个数。

可以发现，要使所有鸽巢都非空，至多只能取 $n$ 个数。当我们取 $n+1$ 个数时，至少有一个鸽巢为空。

因此，取出的数中至少有一对互质的正整数。

例题 2

给出 $n$ 个数的整数序列：$a_1,a_2,\cdots a_n$ ，一定存在连续的子段和能被 $n$ 整除。

证明

记该序列的前缀和为 $s_0,s_1,s_2,\cdots,s_n$ ，其中 $s_k=\sum\limits_{i=1}^{k}a_i$。

这 $n+1$ 个前缀和除以 $n$ 的余数中一定存在两个余数是相同的，即 $s_l\equiv s_r \pmod n$，那么 $a_{l+1}+a_{l+2}+\cdots+a_{r}$ 就能被 $n$ 整除。

Ramsey 定理

在 $6$ 个人中，总有 $3$ 个人相互认识，或者互相都不认识。

这个定理还可以表述为：在 $6$ 个点的完全图 $K_6$ 中，一共有 $15$ 条边，用蓝色和红色给每条边染色。无论如何染色，总存在一个三条边同色的三角形（同色 $K_3$）。

证明

在 $6$ 个点中任取一点 $P$，由鸽巢原理，从 $P$ 点出发的五条边中，至少有 $3$ 条边是同色的，不妨假设为红色。这三条边对应的点设为 $A,B,C$，然后分成两种情况讨论：

因此，可以得出结果，至少存在一个蓝色的 $K_3$ 或者红色的 $K_3$。

矩阵

定义

由 $m \times n$ 个数 $a_{ij}$ 排成的 $m$ 行 $n$ 列的数表称为 $m$ 行 $n$ 列的矩阵，简称 $m \times n$ 矩阵。记作：

\[\displaystyle \begin{bmatrix} a_{11} & a_{12} & a_{13} & ... & a_{1n}\\ a_{21} & a_{22} & a_{23} & ... & a_{2n}\\ a_{31} & a_{32} & a_{33} & ... & a_{3n}\\ ... & ... & ... & ... & ...\\ a_{m1} & a_{m2} & a_{m3} & ... & a_{mn} \end{bmatrix}\]

矩阵的基本运算

加法

\[\displaystyle \left[\begin{array}{lll} 1 & 4 & 2 \\ 2 & 0 & 0 \end{array}\right]+\left[\begin{array}{lll} 0 & 0 & 5 \\ 7 & 5 & 0 \end{array}\right]=\left[\begin{array}{lll} 1+0 & 4+0 & 2+5 \\ 2+7 & 0+5 & 0+0 \end{array}\right]=\left[\begin{array}{lll} 1 & 4 & 7 \\ 9 & 5 & 0 \end{array}\right]\]

矩阵的加法满足下列运算律(A，B，C都是同型矩阵)：

\[\displaystyle \begin{array}{l} A+B=B+A \\ (A+B)+C=A+(B+C) \end{array}\]

应该注意的是只有同型矩阵（两个矩阵 $m_1 \times n_1,m_2 \times n_2$，其中 $m_1 = m_2,n_1 = n_2$）之间才可以进行加法。

减法

\[\displaystyle \left[\begin{array}{lll} 1 & 4 & 2 \\ 2 & 0 & 0 \end{array}\right]-\left[\begin{array}{lll} 0 & 0 & 5 \\ 7 & 5 & 0 \end{array}\right]=\left[\begin{array}{lll} 1-0 & 4-0 & 2-5 \\ 2-7 & 0-5 & 0-0 \end{array}\right]=\left[\begin{array}{ccc} 1 & 4 & -3 \\ -5 & -5 & 0 \end{array}\right]\]

数乘

\[\displaystyle 2 \cdot\left[\begin{array}{ccc} 1 & 8 & -3 \\ 4 & -2 & 5 \end{array}\right]=\left[\begin{array}{ccc} 2 \cdot 1 & 2 \cdot 8 & 2 \cdot(-3) \\ 2 \cdot 4 & 2 \cdot(-2) & 2 \cdot 5 \end{array}\right]=\left[\begin{array}{ccc} 2 & 16 & -6 \\ 8 & -4 & 10 \end{array}\right]\]

矩阵的数乘满足以下运算律：

\[\displaystyle \begin{array}{l} \lambda(\mu A)=\mu(\lambda A) \\ \lambda(\mu A)=(\lambda \mu) A \\ (\lambda+\mu) A=\lambda A+\mu A \\ \lambda(A+B)=\lambda A+\lambda B \end{array}\]

其中 $\lambda,\mu$ 为自然数，$A,B$ 为矩阵。

矩阵相乘

只有在第一个矩阵（$m_1 \times n_1$）的列数和第二个矩阵（$m_2 \times n_2$）的行数相同时（即 $n_1 = m_2$）才有意义。

设 $A$ 为 $P \times M$ 的矩阵， $B$ 为 $M \times Q$ 的矩阵，设矩阵 $C$ 为矩阵 $A$ 与 $B$ 的乘积，

其中矩阵 $C$ 中的第 $i$ 行第 $j$ 列元素可以表示为：

\[C_{i,j} = \sum_{k=1}^MA_{i,k}B_{k,j}\]

通俗的讲，在矩阵乘法中，结果 $C$ 矩阵的第 $i$ 行第 $j$ 列的数，就是由矩阵 $A$ 第 $i$ 行 $M$ 个数与矩阵 $B$ 第 $j$ 列 $M$ 个数分别相乘再相加得到的，所以结果矩阵 $C$ 的大小应该为 $P \times Q$。

矩阵乘法不满足交换律（$A\times B \neq B\times A$，注 $B\times A$ 可能没有意义，不能相乘），但满足结合律（$A \times (B \times C) = (A \times B) \times C$）。

例题

计算：

\[\displaystyle \left[\begin{array}{ccc} 1 & 0 & 2 \\ -1 & 3 & 1 \end{array}\right] \times\left[\begin{array}{ll} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{array}\right]\]
解析
\[\displaystyle \left[\begin{array}{ccc} 1 & 0 & 2 \\ -1 & 3 & 1 \end{array}\right] \times\left[\begin{array}{cc} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{array}\right]=\left[\begin{array}{cc} (1 \times 3+0 \times 2+2 \times 1) & (1 \times 1+0 \times 1+2 \times 0) \\ (-1 \times 3+3 \times 2+1 \times 1) & (-1 \times 1+3 \times 1+1 \times 0) \end{array}\right]=\left[\begin{array}{cc} 5 & 1 \\ 4 & 2 \end{array}\right]\]

矩阵快速幂

对于 行数 等于 列数 的矩阵，可以进行 幂运算。

矩阵乘法满足结合律，不满足一般的交换律。利用结合律，矩阵的幂运算可以利用 快速幂 的思想来优化。

对于快速幂运算

long long binpow(long long a, long long n) {
    long long res = 1, base = a;
    while (n != 0) {
        if (n & 1) res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}

我们可以将其改写为矩阵乘的形式。在此之前，我们需要引入 单位矩阵 的概念。

单位矩阵

在数的概念中，任何数和 $1$ 相乘都等于那个数本身。单位矩阵和 $1$ 的作用相似。通俗的说，任何矩阵与单位矩阵相乘都等于它本身。

单位矩阵 $E$ 是一个方阵，它的主对角线上的所有数均为 $1$，其余位置的数均为 $0$。

\[\displaystyle \left[\begin{array}{cccc} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{array}\right]\]

那么对于 $B=E \times A$，

\[\displaystyle B_{i,j} = \sum_{k=1}^ME_{i,k}A_{k,j}\]

只有当 $k=j$ 时，$E_{i,i}=1$，而其他位置均为 $0$，所以 $B_{i,j}=A_{i,j}$。

同理对于 $B=A \times E$，有 $B_{i,j} = A_{i,j} \cdot E_{j,j}=A_{i,j}$。

因此，任何矩阵与单位矩阵相乘都等于它本身。

应用：加速线性递推

在比赛中，由于线性递推式可以表示成矩阵乘法的形式，也通常用矩阵快速幂来求线性递推数列的某一项。

以斐波那契数列为例。在斐波那契数列中，$ F_{1}=1,F_{0}=0 \quad F_{n}=F_{n-1}+F_{n-2}(i \geq 3)$。

对于“求斐波那契数列的第 $n$ 项”这一问题，在 $n$ 比较小的时候，我们可以通过线性递推直接求解。但当 $n$ 的大小处在 $1e18$ 级别时，线性递推无法求解，此时，我们考虑 矩阵加速递推。

我们看到递推式：

\[\displaystyle F_{n}=F_{n-1}+F_{n-2}\]

等号右边是 $F_{n-1}$ 和 $F_{n-2}$。那么我们首先就可以构造一个矩阵：

\[\displaystyle \left[\begin{array}{ll} F_{n-1} & F_{n-2} \end{array}\right]\]

我们要求出 $F_{n}$ 的值，其实就是需要得到另外一个 $1\times 2$ 的矩阵，那么我们可以把刚才那个矩阵里面的 $n$ 加上 $1$，得到下面这个矩阵：

\[\displaystyle \left[\begin{array}{ll} F_{n} & F_{n-1} \end{array}\right]\]

于是，考虑构造一个转移矩阵 $base$，使得

\[\displaystyle \left[\begin{array}{ll} F_{n-1} & F_{n-2} \end{array}\right] \times \text { base }=\left[\begin{array}{ll} F_{n} & F_{n-1} \end{array}\right]\]

实际上到这里你应该可以理解到这里到底在做什么。实际上我们现在正在推导另一个递推式。我们知道：

\[\displaystyle F_{1}=1,F_{0}=0 \quad F_{n}=F_{n-1}+F_{n-2}(i \geq 3)\]

通过这个递推式去求解 $F_n$ 的值的时间复杂度是 $O(n)$ 的。然而，如果说我们构造出一个对任意 $n$ 都成立的递推式：

\[\displaystyle \left[\begin{array}{ll} F_{n-1} & F_{n-2} \end{array}\right] \times \text { base }=\left[\begin{array}{ll} F_{n} & F_{n-1} \end{array}\right]\]

那么就会有：

\[\displaystyle \left[\begin{array}{ll} F_{1} & F_{0} \end{array}\right] \times \text { base }^{n-1}=\left[\begin{array}{ll} F_{n} & F_{n-1} \end{array}\right]\]

你也会发现，base 这个矩阵里面的元素必须是 常量，或者是其他在递推过程中的 不变量，比如说递推式里面出现的系数等。

根据矩阵乘法的定义，base 是一个 $2 \times 2$ 大小的矩阵。由此我们可以先把这个矩阵写下来：

\[\displaystyle \begin {bmatrix}a,c\\b,d\end{bmatrix}\]

然后根据矩阵乘法的运算法则，就会有：

\[\displaystyle a\times F_{n-1}+b\times F_{n-2} = F_n\] \[\displaystyle c\times F_{n-1}+d\times F_{n-2} = F_{n-1}\]

刚才我们已经说过，base 这个矩阵里面的元素必须是 常量，根据这个要求去得到 $a,b,c,d$ 这四个元素的值。$a,b$ 的值可以由最开始的递推式得到；而 $c,d$ 的值就比较明显了。

于是 base 为

\[\displaystyle \begin {bmatrix}1,1\\1,0\end{bmatrix}\]

在求得 base 之后，这样，我们便可以把 $n=1,2,3,\cdots$ 代入到这个递推式，最后经过迭代，可以得到：

\[\displaystyle \begin {bmatrix}F_{1},F_{0}\end {bmatrix}\times\begin {bmatrix}1,1\\1,0\end {bmatrix}^{n-1} = \begin {bmatrix}F_{n},F_{n-1}\end {bmatrix}\]

最后把 $F_n$ 从矩阵里面取出来就可以了。

于是一个 $O(n)$ 的递推问题就这样优化成了 $O(logn)$，因为

\[\displaystyle \begin {bmatrix}1,1\\1,0\end {bmatrix}^{n-1}\]

可以用 矩阵快速幂 完成。

事实上，这是递推式的一个非常常见的优化。

选择正确的矩阵构造

首先看到原始递推式的等号右边 $a_{n-1},a_{n-2},n^2$，它们都应该在转移矩阵里。于是我们可以得到：

\[\displaystyle A=\begin {bmatrix}a_{n-1},a_{n-2},n^2\end {bmatrix}\]

然后我们需要由这个矩阵进行一次乘法之后推出一个同样是 $1\times 3$ 的矩阵。很明显那个矩阵里面得有 $a_{n}$。而我们在刚才的那个矩阵中对 $n$ 加上 $1$，便可以得到：

\[\displaystyle B=\begin {bmatrix}a_{n},a_{n-1},(n+1)^2\end {bmatrix}\]

于是有：

\[\displaystyle a_n=1\times a_{n-1}+1\times a_{n-1}+1\times n^2\] \[\displaystyle a_{n-1}=0\times a_{n-1}+1\times a_{n-1}+0\times n^2\]

但是 $(n+1)^2$ 这里出现了问题。你无法用 $A$ 矩阵里面的三个元素乘上常系数再求和得到。而 $(n+1)^2=n^2+2\times n+1$，所以如果在矩阵 $A$ 里面再加上 $n,1$ 两个元素就可以了。

于是 $A$ 矩阵变成

\[\displaystyle A=\begin {bmatrix}a_{n-1},a_{n-2},n^2,n,1\end {bmatrix}\]

那么 $B$ 矩阵相应地也需要变成

\[\displaystyle A=\begin {bmatrix}a_{n},a_{n-1},(n+1)^2,n+1,1\end {bmatrix}\]

这样就可以顺利地把矩阵 $C$ 构造出来啦！

当然选项里面还有这么构造的：$A$ 矩阵变成

\[\displaystyle A=\begin {bmatrix}a_{n-1},a_{n-2},n^2,2\times n,1\end {bmatrix}\]

虽然这样也可以得到正确的结果，但是我们一般还是会让 $A$ 里面的所有元素的系数都是 $1$。

数学与动态规划

选择正确的矩阵构造

上面我们主要讲到了怎样去优化一维的递推式，这里我们将讲到如何用矩阵快速幂去优化更复杂一些的 DP 状态转移方程。

统计方案数

依次选取 $n$ 个 $0\sim 3$ 之间的整数，求它们的和是 $3$ 的倍数的方案数对 $10^9+7$ 取模后的结果。

我们令 $f_{i,j}$ 为总共取了 $i$ 个数，且这些数的和对 $3$ 取余的值为 $j$ 的方案数。

状态已经明确，我们先把转移方程写出来：

\[\displaystyle f_{i,0} = 2\times f_{i-1,0}+1\times f_{i-1,1}+1\times f_{i-1,2}\] \[\displaystyle f_{i,1} = 1\times f_{i-1,0}+2\times f_{i-1,1}+1\times f_{i-1,2}\] \[\displaystyle f_{i,2} = 1\times f_{i-1,0}+1\times f_{i-1,1}+2\times f_{i-1,2}\]

然后确认边界状态。

\[\displaystyle f_{0,0} = 1\]

相信你已经看出来状态的第二维，无论问题规模（即 $n$ 的大小）如何，大小都是 $3$。于是我们考虑从这一维入手去构造矩阵。那么，根据上面的转移方程，你首先可以构造出两个 $1\times 3$ 的矩阵：

\[\displaystyle F_i=\begin{bmatrix} f_{i,0} & f_{i,1} & f_{i,2} \end{bmatrix}\]

和

\[\displaystyle F_{i-1}=\begin{bmatrix} f_{i-1,0} & f_{i-1,1} & f_{i-1,2} \end{bmatrix}\]

接下来你需要做的就是构造一个矩阵 base，使得 $F_i=F_{i-1}\times$ base。注意 base 矩阵中的元素一定是 常数。

由此我们可以构造出矩阵 base。

\[\displaystyle base=\begin{bmatrix} 2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2 \end{bmatrix}\]

根据迭代，我们可以得到 $F_n=F_0\times$ base$^{n}$。

路径问题

邻接矩阵

邻接矩阵 $G$ 可以用来表示一张图，通常用二维数组来实现。

在邻接矩阵 adj 中，adj[u][v]=w代表从点 $u$ 到点 $v$ 的距离为 $w$。

邻接矩阵是一类矩阵，通过矩阵的特性，我们可以用它来解决一类图上的问题。

定长路径统计

给一个 $n$ 个点的有向图，每条边的边权均为 $1$，然后给一个整数 $k$，你的任务是对于所有点对 $(u,v)$ 求出从 $u$ 到 $v$ 长度为 $k$ 的路径的数量。（可能存在重边或自环，所求的结果 不一定 是简单路径，即路径上的点或者边可能走多次）

解析

我们将这个图用邻接矩阵 $G$（对于图中的边 $(u\to v)$，令 $G[u,v]=1$，其余为 $0$ 的矩阵；如果有重边，则设 $G[u,v]$ 为重边的数量）表示这个有向图。下述算法同样适用于图有自环的情况。

显然，该邻接矩阵对应 $k=1$ 时的答案。

假设我们知道长度为 $k$ 的路径条数构成的矩阵，记为矩阵 $C_k$。显然 $C_0$ 就是单位矩阵 $E$。在已知 $C_k$ 的情况下，我们想求 $C_{k+1}$ ，只要将其与邻接矩阵 $G$ 相乘，根据乘法原理，就可以计算出 $i$ 点经过点 $p$ 到达点 $j$ 的路径方案数：

\[C_{k+1}[i,v] = \sum_{p = 1}^{n} C_k[i,p] \cdot G[p,j]\]

我们可以把它看作矩阵乘法的运算，于是上述转移可以描述为

\[C_{k+1} = C_k \cdot G\]

那么把这个递推式展开可以得到

\[C_k = \underbrace{G \cdot G \cdots G}_{k \text{ 次}} = G^k\]

因此我们可以利用矩阵快速幂，在 $O(n^3 \log k)$ 的复杂度内计算结果。

定长最短路问题

给你一个 $n$ 阶加权有向图和一个整数 $k$。对于每个点对 $(u,v)$ 找到从 $u$ 到 $v$ 的恰好经过 $k$ 条边的最短路的长度。（可能存在重边或自环，所求的结果不一定是简单路径，即路径上的点或者边可能走多次）

解析

我们仍构造这个图的邻接矩阵 $G$，$G[i,j]$ 表示从 $i$ 到 $j$ 的边权。如果 $i,j$ 两点之间没有边，那么 $G[i,j]=\infty$ 。（有重边的情况取边权的最小值）

显然上述矩阵对应 $k=1$ 时问题的答案。我们仍假设我们知道 $k$ 的答案，记为矩阵 $L_k$。现在我们想求 $k+1$ 的答案。显然有转移方程

\[\displaystyle L_{k+1}[i,j] = \min_{1\le p \le n} \left\{L_k[i,p] + G[p,j]\right\}\]

事实上我们可以类比矩阵乘法，你发现上述转移只是把矩阵乘法的乘积求和变成相加取最小值，于是我们定义这个运算为 $\odot$ ，即

\[\displaystyle A \odot B = C~~\Longleftrightarrow~~C[i,j]=\min_{1\le p \le n}\left\{A[i,p] + B[p,j]\right\}\]

于是得到

\[\displaystyle L_{k+1} = L_k \odot G\]

展开递推式得到

\[\displaystyle L_k = \underbrace{G \odot \ldots \odot G}_{k\text{ 次}} = G^{\odot k}\]

我们仍然可以用矩阵快速幂的方法计算上式，因为它显然是具有结合律的。只需要把矩阵乘法中的res.a[i][j] += a.a[i][k] * b.a[k][j];改为res.a[i][j] = min(res.a[i][j], a.a[i][k] + b.a[k][j]);即可求解，时间复杂度 $O(n^3 \log k)$ 。

限长路径最短路

上述两个问题的算法只适用于边数固定的情况。然而我们可以通过改进算法，解决边数小于等于 $k$ 的情况。具体地，考虑以下问题：

给一个 $n$ 阶有向图，边权为 $1$ ，然后给一个整数 $k$ ，你的任务是对于每个点对 $(u,v)$ 找到从 $u$ 到 $v$ 长度小于等于 $k$ 的最短路径。

解析

我们简单修改一下这个图，我们给每一个结点加一个权值为 $0$ 的自环。这样走的时侯就可以走自环，相当于原地走。这样就包含了小于等于 $k$ 的情况。修改后再做矩阵快速幂即可。（即使这个图在修改之前就有自环，该算法仍是成立的）。

抽屉原理

前面，我们讲到抽屉原理最为重要的用途 —— 证明一些简单的结论。其中，我们提到了这样一条结论：

给出 $n$ 个数的整数序列：$a_1,a_2,\cdots a_n$，一定存在连续的子段和能被 $n$ 整除。

实际上，我们可以对这个结论进行扩展：给出 $n$ 个数的整数序列 $a_1,a_2,\cdots a_n$，一定存在连续的子段和能被 $k(1\le k\le n)$ 整除。

所以对于刚才的题目而言，当 $n\ge m$ 的时候，原数列中一定有一个连续子段的和是 $m$ 的倍数，就不需要再进行计算了。至于 $n<m$ 的情况，使用背包就可以完成了。

由此，整个问题的复杂度由 $O(nm)$ 缩小为 $O(m^2)$。

这就是抽屉原理在 DP 问题中最重要的应用之一 —— 通过一些简单的结论，使用特判等方式去缩小问题的规模。

数学推导

分类讨论

例题 1

给定一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$，数组 $a$ 和 $b$ 中的数在同一数组中只会出现一次，可以执行以下两种操作：

  1. 花费 $x$，删除连续 $k$ 个数；

  2. 选择两个相邻的数，花费 $y$ 删除其中较小的一个数；

问能否通过这些操作把数组 $a$ 变为数组 $b$，如果能，求最小的花费。

输入格式

第一行为两个整数 $n,m$。

第二行为三个整数 $x,k,y$。

第三行为 $n$ 个整数，即序列 $a$ 里面的元素。

第四行为 $m$ 个整数，即序列 $b$ 里面的元素。

输出格式

只有一个数，为最小的花费。当然如果无法构造，输出 $-1$。

样例输入

5 2
5 2 3
3 1 4 5 2
3 5

样例输出

8
解析

可以发现，当 $b$ 不是 $a$ 的子序列时，无法把 $a$ 变成 $b$。

否则，可以利用数组 $b$ 把数组 $a$ 分割成若干个子区间，对于每个子区间，有如下两种情况。

但是这样就正确了吗？

回到题目。我们询问的不是有没有 合法方案，而是还需要在方案中寻找花费最少的方案。从区间里面删除连续的 $k$ 个数，我们可以执行一次 $1$ 操作，但是也可以执行 $k$ 次 $2$ 操作。

所以我们要判断执行一次 $1$ 操作，和执行 $k$ 次 $2$ 操作，哪个的代价更小。当执行一次 $1$ 操作的代价更小的时候，按照上一页所说的操作即可。

那么，当执行 $k$ 次 $2$ 操作的代价更小的时候，该怎么办呢？

当执行 $k$ 次 $2$ 操作的代价更小的时候，是不是执行 $len$ 次 $2$ 操作就行了呢？如果这个区间里面所有的数都比两边的数要小，是可以的。

但是如果该区间存在比两边都大的数，只执行 $2$ 操作，是不能把区间里面所有的数删干净的，所以需要留下 $k$ 个数去执行 $1$ 操作。

总结

例题 1 已经算是比较复杂的分类讨论了，总共分了三步才讨论完了所有的情况。

分类讨论其实是很难去总结出一个行之有效的套路的，因为题目的场景多种多样，并且还可能会结合到我们之前已经学过的各种知识。在考场上，对于一个细节很多，情况很复杂的题目，其实你很难保证天衣无缺，所以事后的检验是非常重要的。

你需要牢记批量制造随机数据来对拍的方法。一般来讲，分类讨论中如果遗漏了一些情况，在批量制造随机数据进行检查之后就能检查出错误。

例题 2

给定一个长度为 $n$ 的环，$a_i$ 代表第 $i$ 个位置的类型。

现在让你用最小的颜色种类（颜色从 $1$ 开始），去给这个环染色。

要求：如果环中相邻的 $2$ 个类型不同，则需要将这两位染为不同的颜色。

思路建议：什么时候只需要一种颜色，什么时候只需要两种颜色，什么时候只需要三种颜色…

样例输入

3
1 2 3

样例输出

3
解析

考虑分类讨论。

康托展开

设有 $n$ 个数 $(1,2,3,4,…,n)$ ，把 $1 \sim n$ 的所有排列按字典序排序，这个排列的位次就是它的排名。

康托展开可以在 $O(n^2)$ 的复杂度内求出一个排列的排名。

举例

我们知道长为 $5$ 的排列 $[2,5,3,4,1]$ 大于以 $1$ 为第一位的任何排列，以 $1$ 为第一位的 $5$ 的排列有 $4!$ 种。

对第二位的 $5$ 而言，它大于 第一位与这个排列相同的，而这一位比 $5$ 小的 所有排列。不过我们要注意的是，这一位不仅要比 $5$ 小，还要满足没有在当前排列的前面出现过，不然就 不符合排列的定义 了。因此这一位为 $1,3$ 或 $4$ ，第一位为 $2$ 的所有排列都比它要小，数量为 $3\times 3!$ 。

按照这样统计下去，答案就是 $1+4!+3\times 3!+2!+1=46$ 。注意我们统计的是排名，因此最前面要 $+1$ 。

实现

通过上面的例子我们可以发现，对于一个排列，我们要求解它在全排列中的排名，只要对每一位计算 比当前位小，且没有在之前位出现过的元素 组成的所有排列，求和即可。

答案即为：

\[\displaystyle \text {ans}=1+\sum_{i=1}^{n} p_{i} \times (n-i) !\]

其中 $p_i$ 表示 比当前位小，且没有在之前位出现过的 元素个数。

逆康托展开

因为排列的排名和排列一一对应，所以康托展开满足双射关系，是可逆的。

即：我们知道一个长度为 $n$ 的排列的排名为 $k$，我们就可以求出这个长度为 $n$ 的排列。

举例

对于我们之前提到的排列 $[2,5,3,4,1]$，它的排名为 $46$，我们可以通过排名逆推出这个排列。

具体的，首先让 $46-1=45$，$45$ 代表着有多少个排列比这个排列小。 $\left\lfloor \frac {45}{4!}\right\rfloor + 1 = 2$，所以第 $1$ 位应该选可选的数中第 $2$ 小的，所以排列的第 $1$ 位是 $2$。

此时让排名减去 $1\times 4!$ 得到 $21$，$\left\lfloor \frac {21}{3!}\right\rfloor + 1 = 4$，所以第 $2$ 位应该选可选的数中第 $4$ 小的，所以排列的第 $2$ 位是 $5$（数字 $2$ 已经在第一位用过了）。

$21-3\times 3!=3$，$\left\lfloor \frac {3}{2!}\right\rfloor + 1 = 2$，所以第 $3$ 位应该选可选的数中第 $2$ 小的，所以排列的第 $3$ 位是 $3$（数字 $2$ 已经在第一位用过了）。

当剩下最后两位没填的时候，此时发现排名为 $1$，所以倒数第 $2$ 位是剩下两个数中的较大者，也就是 $4$，而最低位是 $1$。

实现

那么我们就得到了逆康托展开的求解方式：

按位构造

例题

从区间 $[l,r]$ 内选出 最多 $k$ 个数，使得他们的异或和最小。

样例输入

5 12 3

样例输出

0

注：在选取 $12,11,7$ 时可以得到 $0$。

解析

对于一个偶数 $2x$，$2x$ 异或 $2x+1$ 可以得到 $1$ 。

那么 $2x,2x+1,2x+2,2x+3$ 异或就得到了 $0$，这意味着在 $k \ge 4$ 时，取这样的四个数就能使异或和为 $0$。

我们注意到 $r-l+1 \ge 5$ 时，一定存在这样的四元组。那么对 $r-l+1 \le 4$ 的情况，我们可以选择暴力求解答案。

那么我们只要对 $r-l+1 \ge 5$，$k < 4$ 的情况进行讨论：

我们不妨设 $x > y > z$，那么对于最高位，一定有 $x,y$ 的最高位为 $1$，$z$ 的最高位为 $0$；

\[\displaystyle \begin{array}{l} x\ 1 \ldots \\ y\ 1 \ldots \\ z\ 0 \ldots \end{array}\]

对于次高位，有三种情况：

\[\displaystyle \begin{array}{l} x\ 11 \ldots \\ y\ 10 \ldots \\ z\ 01 \ldots \end{array} \begin{array}{l} x\ 11 \ldots \\ y\ 11 \ldots \\ z\ 00 \ldots \end{array} \begin{array}{l} x\ 10 \ldots \\ y\ 10 \ldots \\ z\ 00 \ldots \end{array}\]

其中如果 $z$ 的次高位为 $0$，那么为了使 $x,y,z$ 的值尽可能接近，我们将原本的 $x,y$ 最高位变为 $0$，次高位变为 $1$，仍然是一组合法的解；那么次高位一定是这样：

\[\displaystyle \begin{array}{l} x\ 11 \ldots \\ y\ 10 \ldots \\ z\ 01 \ldots \end{array}\]

要使 $x,y,z$ 尽可能接近，我们可以让最大值尽可能小，最小值尽可能大，所以最后的 $x,y,z$ 应该形如：

\[\displaystyle \begin{array}{l} x\ 1100000 \ldots \\ y\ 1011111 \ldots \\ z\ 0111111 \ldots \end{array}\]

因此我们只需要找到第一个 $z \ge l$，判断对应的 $x$ 是否 $\le r$ 即可。

差分与前缀和

例题 1

给定一个长为 $n(n \le 10^5)$ 的序列 $c$，定义一次操作为将 $c_i(1<i<n)$ 变为 $c_{i-1}+c_{i+1}-c_i$。再给一个长为 $n$ 的序列 $t$，问序列 $c$ 能否通过一系列操作变为序列 $t$。

$(0 \le c_i,t_i \le 2 \times 10 ^ 9)$

样例输入 1

$c = {1,2,3,4,5}$

$t = {5,4,3,2,1}$

样例输出 1

no

样例输入 2

$c = {1,2,4,7,11}$

$t = {1,5,8,10,11}$

样例输出 2

yes，操作序列为 ${2,3,4,2,3,2}$

解析

定义差分数组 $d_i=c_{i + 1} - c_i$，如果我们此时对于 $c_i$ 进行操作，即 $c’i=c{i-1}+c_{i+1}-c_i$，那么对于 $d_i$ 我们将得到：

\[\displaystyle \begin{array}{l} d_{i-1}^{\prime}=c_{i}^{\prime}-c_{i-1}=\left(c_{i+1}+c_{i-1}-c_{i}\right)-c_{i-1}=c_{i+1}-c_{i}=d_{i} \\ d_{i}^{\prime}=c_{i+1}-c_{i}^{\prime}=c_{i+1}-\left(c_{i+1}+c_{i-1}-c_{i}\right)=c_{i}-c_{i-1}=d_{i-1} \end{array}\]

也就是说，我们对 $c_i$ 进行一次操作，在差分数组中的体现，只不过是将 $d_i-1$ 和 $d_i$ 的值交换了。这意味着，如果我们把差分数组看做是无序的，那么它将是永远不会变化的。

因此，我们只要把 $c$ 和 $t$ 数组的差分数组求出来，如果排序后两个数组完全相同那么意味着有解（注意：我们首先还需要判断是否满足 $c_1=t_1,c_n=t_n$，因为 $c_1$ 和 $c_n$ 是不会变化的），否则就是无解。

约数与倍数

例题 1

对于一个数 $x$，定义 $x$ 是 nice number 当且仅当 $x \% b \neq 0$，且 $x \% b$ 能整除 $\lfloor \frac{x}{b} \rfloor$，且 $\frac{\lfloor \frac{x}{b} \rfloor}{x\%b}$ 的结果在 $1\sim a$ 之间。

现在给定 $a,b$，求所有 nice number 的和。

样例输入

a = 2,b = 2

样例输出

8,两个 nice number 分别为 3 和 5。
解析

令 $x=db+m$，则有 $d=mk$

那么有 $x=mkb+m=(kb+1)m$，而 $m \in[1,b-1], k \in[1,a]$

那么有 $\sum x=\sum_{k=1}^a(k\cdot b+1)\cdot \sum_{m=1}^{b-1}m$

答案即为 $\sum x=\frac{b \cdot(b-1)}{2}\left[(b+1) \cdot a+\frac{a \cdot(a-1)}{2} \cdot b\right]$

例题 2

给出一个长度为 $n(1 \le n \le 10^5)$ 的数组 $a$，再给出一个长度为 $m(1 \le m \le 10^5)$ 的数组 $b$，现在要求输出，当 $j=1,2, \ldots, m$ 时，$gcd(a_1+b_j,a_2+b_j,…,a_n+b_j)$ 的答案。

解析

根据错位相减法，有 $gcd(x,y)=gcd(x,x-y)$。

首先我们对数组 $a$ 排序，保证 $a_i \le a_{i+1}$，那么对 $a_i(1 \le i < n)$ 有

\[\displaystyle \begin{aligned} & g c d\left(a_{i}+b_{j}, a_{i+1}+b_{j}\right) \\ =& g c d\left(a_{i}+b_{j},\left(a_{i+1}+b_{j}\right)-\left(a_{i}+b_{j}\right)\right) \\ =& g c d\left(a_{i}+b_{j}, a_{i+1}-a_{i}\right) \end{aligned}\]

所以答案即为：

\[\displaystyle \begin{aligned} & g c d\left(a_{1}+b_{j}, a_{2}+b_{j}, \ldots, a_{n-1}+b_{j}, a_{n}+b_{j}\right) \\ =& g c d\left(a_{1}+b_{j}, a_{2}+b_{j}, \ldots, a_{n-1}+b_{j}, a_{n}-a_{n-1}\right) \\ ...\\ =& g c d\left(a_{1}+b_{j}, a_{2}-a_{1}, \ldots, a_{n-1}-a_{n-2}, a_{n}-a_{n-1}\right) \end{aligned}\]

例题 3

给定一个正整数 $x(x \ge 5)$，构造一个集合 $S={a_1,a_2,…,a_n}$，有如下要求：

现在要使这些数的最大值减最小值 $(a_{max}-a_{min}) $ 最小，求 $(a_{max}-a_{min})$ 的最小值。

样例输入

10

样例输出

2 3 5
解析

当且仅当 $x=6$ 时无解。

否则首先对奇偶分类，对于奇数，显然有 $S={\lfloor \frac{x}{2} \rfloor, \lfloor \frac{x}{2} \rfloor + 1}$，答案为 $1$ 。

对于偶数，有以下几种情况：

这几道例题中涉及到了取余（同余），最大公约数和互质等相关的性质。

实际上对于任意的两个正整数 $x,y$，我们可以用 $y = ax+b(a \ge 0,0\le b<x)$ 的形式去进行表示，其中 $a,b$ 也是整数，而 $b$ 是 $y$ 对 $x$ 取模之后的结果。而如果 $y$ 是 $x$ 的倍数，则可以简化为 $y=ax$。

这样转化的作用，即是将题面中所有需要对 $x$ 进行取模（或者是 $x$ 的倍数）的量进行统一的表示，进而利用余数的各种性质（例如关于加法，减法和乘法运算的性质）等去解决问题。

然后是最大公约数。相信大家都知道 辗转相除法。辗转相除法实际上是基于：

\[\displaystyle gcd(a,b) = gcd(b, a \%b)\]

这个式子的。如果我们令 $a>b$，那么明显有：

\[\displaystyle gcd(a,b) = gcd(b, a \%b) = gcd(b, (a-b) \%b) = gcd(a-b, b)\]

所以我们可以用辗转相除法去进行一些等价转换。而通过这个等价转换，我们可以得到一个新的推论：

$ gcd(a, b) a-b $ ，因为 $ gcd(a, b) = gcd(a-b, b) $ 。

由此我们可以推导出一些互质数的性质：

  1. 两个相邻的整数互质。
  2. 两个相邻的奇数互质。
  3. 实际上，当 $a$ 和 $b$ 的差为质数的时候，若 $a,b$ 都不是这个质数的倍数，那么它们互质。

我们只列举出了一些最为常见的性质便于大家去进行构造等操作。在以后的练习中你们还会遇到更多，你需要依靠自己去发掘和积累。

图论建模

序列问题

在一个长度为 $n$ 的序列中，每一个元素都是int范围内的正整数。现在可以进行若干次操作，每一次操作你可以选择任意的一个偶数 $c$ 并且将这个序列中所有等于 $c$ 的元素除以 $2$ 。

例如，当序列为: $[1,2,3,4,5,4,3,2]$ 时。如果选择 $2$ 进行操作，那么操作后序列变为: $[1,1,3,4,5,4,3,1]$ 。

现在你需要把这个序列中的元素全部变为奇数，求最小的操作次数。

我们现在考虑如何将这个问题转化为图论问题。

我们每一次操作可以将一个偶数的值除以 $2$ ，这就提示了我们用边来表示一种变化，用点来表示数值。

例如对于值 $8$ ，我们可以得到下面的图：

表示 $8$ 可以通过一次操作得到 $4$ , 再进行一次操作得到 $2$ , 再进行一次操作可以得到 $1$ 。在点 $1$ 时，由于该点是奇数，不能进行操作，所以没有出边。

同样地，对于值 $12$ ，可以得到：

假如我们将所有正整数的值构成的图全部画出，可以发现：这个图是由若干条链组成的，每一条链都有且仅有一个点是奇数，并且这个点是链的终点。

那么我们就可以将问题转化为：有若干个人在图上，每一次操作可以让一个点上的所有人沿着有向边前进一个单位。我们需要让所有人都走到其所在链的终点。

现在我们已经成功将原问题转化为了图论模型，做法显而易见：从每一个点开始搜索该点到链终点的路径，并且标记路径上所有的偶数点。最终的答案就是被标记的点的个数（注意点会被重复标记）。

例如对于序列： $[4,2,12]$

被标记的点为： $4,2,12,6$ ，所以答案为 $4$ ，也就是需要操作 $4$ 次。

食客问题

有 $n$ 个味道各不相同的糖果和 $k$ 个小朋友。每个小朋友都恰好喜欢两种不同味道的糖果。现在让所有小朋友排成一队并依次取糖果，每个小朋友都会把自己喜欢的糖果全部取走。如果轮到一个小朋友取糖果时，他无法找到自己喜欢的糖果，那么他会非常沮丧并且不会取糖果。

现在让你给小朋友安排一个排队的顺序，使得沮丧的小朋友的人数最小。输出这个最小值。

注意到每个小朋友都恰好喜欢两种不同味道的糖果，一张图中的每条边也恰好连接两个顶点。这就在提示我们用边来表示每个小朋友。

我们可以用 $n$ 个味道各不相同的糖果来对应 $n$ 个点，每个喜欢第 $x_i$ 个和第 $y_i$ 个糖果的小朋友对应一条连接 $x_i$ 与 $y_i$ 的无向边。

例如有 $4$ 个糖果 $4$ 个人，这四个人喜欢的糖果分别是 $[1,2],[1,3],[1,4],[2,3]$ ，则建出的图为：

这样我们就可以将原问题转化为：按照一定的顺序将图中的边删去，每条边被删除时，该边连接的顶点也会被删除。如果一条边的两个顶点都已经被删除，那么该边便不可被删除。我们需要合理安排一个删边顺序使得不可被删除的边的数量最少。

显然我们可以以连通块为单位进行考虑，不同的连通块之间不会互相影响。

现在我们考虑一个有 $c$ 个点的连通块，我们知道第一次在该连通块内删边一定会删去两个点，第二次及之后在该连通块内删边会删去 $1$ ~ $2$ 个点。所以在最优情况下， $c$ 个点的连通块最多可以满足我们删去 $c-1$ 条边（第一条边删去两个点，之后的边都只删除一个点）。

那么这个最优情况一定能取到吗？

假如一个点数为 $c$ 的连通块被 $c-1$ 条边连在一起，我们可以发现此时该连通块构成了树结构。

可以发现：如果我们删除了第一条边（假设该边连接了 $u,v$ 两个点），那么此时该图会被分裂为两棵树。我们可以让这两棵树分别以 $u$ , $v$ 为根，然后按照深度从小到大的顺序，一层一层地删除边。

如下图：（边上的序号代表该边被删除的顺序）

这种方法是最优的，因为它达到了理论上界，也就是在一个有 $c$ 个点的连通块内删去了 $c-1$ 条边。

我们知道任意一个连通块都可以看作是一棵树加若干条其他边，所以任何一个连通块都可以应用这样的删边方法。于是我们可以得出结论：任何一个大小为 $c$ 的连通块，最多可以删去 $c-1$ 条边。

所以最多可以删除的边可以用这样的公式来表示（设 $d$ 为连通块个数）： \(\displaystyle \sum_{c\text{ 是连通块}}(size(c)-1) = \sum_{c\text{ 是连通块}} size(c)-d = n-d\)

也就是说，可以删除的最多的边的个数为 $n - \text{连通块个数}$ 。

所以做法就很显然了，我们将图建出之后，用 DFS 找出这张图的连通块个数就可以得到答案。

如何进行建图

我们刚才练习了两道题目，现在来回顾一下我们解决问题的过程。

  1. 分析题目中含有的性质并进行推导
  2. 将图中给出的问题转化为图论模型，并且进行建图
  3. 在这个图中解决该问题

可以看出，比较难的一步就是第二步，也就是如何将原问题转化为一个图论的模型。在这一步，我们需要考虑图中的点对应题目中的哪些元素、边对应题目中的哪些元素。

一般来说，在无向图中可以把边看作是一些元素之间具有的联系，例如之前的食客问题：用点来对应糖果，边来对应小朋友。当两条边连接同一个点时，就代表他们产生了联系（冲突）。在对这种图进行建图时，可以从考虑边的意义入手。

在有向图中，更多地我们可以用点来对应状态，有向边来对应状态的转移。例如在第一个题中，我们的点对应就是数字，每条边表示的就是从 $x$ 到 $\frac x2$ 的转移。在对这种图进行建图时，可以从考虑点的状态入手。

我们为什么要将原题转化为图论模型再进行解决呢？

实际上无论我们是在原题上进行推导，还是在转化后的图论模型中进行推导，都是等价的。但是转化为图论模型可以使问题更加直观，也便于我们应用所学过的图论算法。

我们在后面会看到，可以将一些特殊形式的不等式组转化为图论模型，并且使用最短路算法来求出满足不等式组的一组解。

小 K 的农场

小 K 在 MC 里面建立很多很多的农场，总共 $n$ 个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共 $m$ 个），以下列三种形式描述：

但是，由于小 K 的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式

第一行包括两个整数 $n$ 和 $m$，分别表示农场数目和小 K 记忆中的信息的数目。

接下来 $m$ 行：

输出格式

如果存在某种情况与小 K 的记忆吻合，输出 “Yes”，否则输出 “No”。

样例输入

3 3
3 1 2
1 1 3 1
2 2 3 2

样例输出

Yes

这一类问题是一种比较经典的模型：差分约束系统

我们用 $s_i$ 来表示农场 $i$ 中的作物数量，那么我们就可以将题目中给出的三种形式表示为：

由不等式知识可以得知，其中：

这样我们就将这三种形式全部转化为了形如 $x - y \le c$ 的形式，这恰好是 差分约束算法 可以解决的问题。

差分约束

差分约束系统 是一种特殊的 $n$ 元一次不等式组，就像我们上一节中说的形如 $x_a-x_b\le c_k$ 的不等式组。其中的 $c_k$ 是常数，可以为正数、负数或者 $0$ 。

我们要解决的问题就是：求一组解 $x_1=a_1,x_2=a_2,\cdots,x_n=a_n$，使得所有约束条件都被满足，或者判断出该不等式组无解。

注意到差分约束系统中的每个约束条件 $x_i-x_j \le c_k$ 都可以变形成 $x_i\le x_j +c_k$ ，这与最短路中的不等式 $dist[y] \le dist[x] + z$ 非常相似。

因此，我们可以把每个变量 $x_i$ 看做图中的一个顶点，对于每个约束条件 $x_i-x_j\le c_k$ ，从顶点 $j$ 向顶点 $i$ 连一条长度为 $c_k$ 的有向边。

例如不等式 $x_1 - x_2 \le 3$ 在图中表示为：

我们可以设 $dist[0] = 0$ ，从 $0$ 向每个点连一条权重为 $0$ 的有向边，然后跑单源最短路。当最短路计算结束后， 我们就可以得到一组可行的解 $x_i = dist[i]$ 。

因为最短路求出来的解肯定满足 $dist[i] \le dist[j] + cost(j,i)$ （其中 $cost(j,i)$ 是从 $j$ 到 $i$ 的有向边的边权），也就是满足我们最初的约束条件 $x_i-x_j\le c_k$ 。

同学们可以思考一下，什么时候差分约束系统无解呢？

由于差分约束系统与我们当前的图的最短路相对应，所以当最短路无解时，该差分约束系统无解。即图中存在负环时，该差分约束系统无解。

求解差分约束系统的最短路时，我们一般都会选择使用 SPFA 算法。因为 SPFA 可以求出带负权边的图的最短路，并且可以判断图中是否存在负权环。

差分约束的一些应用

狡猾的商人

刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了 $n$ 个月以来的收入情况，其中第 $i$ 个月的收入额为 $A_i(i=1,2,3,\cdots,n-1,n)$ 。当 $A_i$ 大于 $0$ 时表示这个月盈利 $A_i$ 元，当 $A_i$ 小于 $0$ 时表示这个月亏损 $A_i$ 元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。 刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出来，每次偷看账本时她都只能看某段时间内账本上记录的收入情况，并且她只能记住这段时间内的总收入。 现在，刁姹总共偷看了 $m$ 次账本，当然也就记住了 $m$ 段时间内的总收入，你的任务是根据记住的这些信息来判断账本是不是假的。

这是一个比较简单的转化问题，刁姹得到的信息形式为： 从 $u$ 到 $v$ 这段时间内总盈利为 $c$ 元。

我们可以做一个前缀和，令 $s_n=\sum_{i=1}^nA_i$ ，所以刁姹得到的信息可以使用下面的不等式来表示：

\[\displaystyle s_v-s_{u-1} \le c, s_v-s_{u-1}\ge c\]

这两个不等式就是我们在 小 K 的问题 中遇到过的不等式，同学们可以尝试自己将这个不等式转化为差分约束的标准形式。

转化为上面的不等式形式后，就可以直接应用差分约束算法来进行求解。

应用差分约束的关键就是将原题中给出的条件用只包含两个变量的不等式来进行表示，所以需要我们合理设计变量表示的状态。

好比这道题，如果是将每个月的收入额作为变量，那么每一条信息都有可能涉及 $1$ ~ $n$ 个变量，这显然是我们无法用差分约束算法直接解决的。但是如果我们将前缀和作为变量，那么每一条信息都只需要用涉及两个变量的不等式来表示，这样就可以用差分约束算法来解决了。

合法判定

有 $n$ 个变量（都是整数），$m$ 个关系。一共有三种关系：

现在给出这 $m$ 个关系，每一个关系都是上述关系的其中之一。你需要将这 $n$ 个变量从小到大排序。

经过刚才的学习，我们知道了 $x_a-x_b\le c_k$ 可以转化为最短路模型。接下来我们来看一下这三种关系：

问题就变成了我们怎么对这三个式子进行转化，让它们变成 $x_a-x_b\le c_k$ 这样的不等式。

由于 $n$ 个变量都是整数，那么 $a<b$ 就可以转化为 $a-b\le -1$。

类似地，$a>b$ 可以转化为 $b-a\le -1$。

最后就剩下了 $a=b$。对于 $a=b$ 这个表达式，它实际上等价于下面两个不等式（同时成立）：

（P.S. 这个等价关系是一个用来证明两个量相等的常见方式）

由此，根据 $a=b$ 我们可以列出 $a-b\le 0$ 和 $b-a\le 0$ 两个不等式。这样我们就把题目中的三种关系成功地转化为了带小于等于号的不等式，这样就可以用差分约束系统完成了。

那么这道题是不是只有这一种做法呢？不是的。实际上，如果不存在 $a=b$ 的情况，当出现一个 $a<b$ 的关系的时候从 $a$ 往 $b$ 连一条边，这道题可以非常轻松地用拓扑排序直接完成。

那么出现 $a=b$ 的时候该怎么办呢？其实还是可以用拓扑排序解决的，只不过我们首先需要确认出哪些变量值相等。在下一个阶段的一开始，我们将会学习到关于 图的连通性 的一些概念和算法，到时候你就可以高效地解决这个问题了。

复杂背包问题

掷骰子

有 $d$ 个不一样的骰子，每个骰子上都有 $f$ 个面，分别标号为 $1,2,\cdots, f$。

我们约定：掷骰子得到的总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 $target$ ，请你计算出有多少种不同的组合情况（所有的组合情况共有 $f^d$ 种，答案模 $10^9+7$。

$1 \le d,f \le 30$，$1 \le target \le 1000$

我们尝试将这道题转化为背包模型。

比较容易看出来，我们可以将点数作为背包模型中的背包容量和物品大小，然后用背包 dp 的方式来计算不同组合的情况。

在一个常规的背包问题中，我们可以用 $f_i$ 来表示选择总大小为 $i$ 的物品的方案数量。这样当我们往里面放一个大小为 $j$ 的物品时，就可以通过转移f[i+j] += f[i]来进行更新。

接下来我们考虑将题目中的骰子转化为物品。

每个骰子可能投出 $1,2,\cdots, f$ 点，所以我们将每个骰子转化为 $f$ 个物品，点数分别为 $1, 2, \cdots, f$。

但是注意到这样的转化有一定的问题：一个骰子会转化为 $f$ 个物品，这个 $f$ 个物品中我们只能选择一个物品，因为骰子肯定只有一面能够朝上。所以我们无法直接套用我们之前学过的背包算法，我们需要一个新的背包算法，用来解决像这种在同一组中只能选择一个物品的问题。

分组背包

分组背包的定义很简单：就是将所有物品分组，组内物品相互冲突，最多只能选一个物品放入背包中。

我们在上一节中遇到的问题，实际上就是一个比较特殊的分组背包问题（每一组内必须选择一个物品，因为骰子一定会有一面朝上）。

分组背包的实质是灵活使用 01 背包，在进行 01 背包时，我们会依次考虑某一个物品是否被选择来进行 dp，然后下一个物品在上一次 dp 的结果中考虑，即 01 背包是如下的代码：

for(int i = 1; i <= n; ++i){
    for(int j = m; j >= w[i]; --j){
        dp[i][j] += dp[i - 1][j - w[i]];
    }
}

这就提醒了我们，可以将分组背包看作以组为单位的 01 背包，以组为单位来进行 dp 结果的保存。考虑组内的物品时，始终使用上一组的 dp 数组来进行转移，这样就可以保证这一组内的物品不会被重复选取。

代码如下：

for(int i = 1; i <= d; ++i){ // 枚举组
    for(int j = 1;j <= f; ++j){ // 枚举组内的所有物品
        for(int k = target;k >= j; --k){ // 枚举背包大小进行转移
            dp[i][k] += dp[i-1][k-j]; // 从 dp[i-1] 进行转移
        }
    }
}

接下来我们考虑分组背包的空间优化，与 01 背包相似，分组背包的dp[i][j]表示的是在 $1$ ~ $i$ 组中进行选择，总物品大小为 $j$ 的方案数。

我们知道在 01 背包中，可以直接用dp[j]来表示总物品大小为 $j$ 时的答案。类似地，在分组背包中我们也可以做出相应的优化。

但是为了保证分组背包 dp 的正确性，我们需要调整枚举顺序，使得每一次转移时等号右侧始终表示上一组的状态。

代码如下:

for(int i = 1; i <= d; ++i){ // 枚举组
    for(int k = target; k >= 0; --k){ // 枚举背包体积进行转移
        dp[k] = 0; // dp[k] 是采取累加方式来记录的，所以需要进行初始化
        for(int j = 1; j <= f && j <= k; ++j){ // 枚举组内的所有物品，注意这里加入了 j <= k 的判断
            dp[k] += dp[k - j]; // 此时 dp[k-j] 一定表示上一组的状态
        }
    }
}

购买物品

FJ 将要去商店购买物品，他需要一些盒子来装不同的物品。每一个盒子都只能装一些特定的物品。也就是说，在购买一个物品之前，你需要先购买特定的盒子。如果你购买了一个盒子，那么你可以装下所有该盒子可以装的物品。

输入第一行有两个正整数 $n, w$，表示有 $n$ 个盒子，总共拥有的钱数量为 $w$ 。

之后输入 $n$ 行，每一行首先有两个正整数 $p_i, m_i$，分别表示这个盒子的价格和这个盒子能够装下的物品种类个数。之后该行会有 $m_i$ 对正整数 $c_j,v_j$，第 $j$ 对数描述这个盒子能够装下的第 $j$ 个物品的价格 $c_j$ 和价值 $v_j$ ，注意每个物品都只有一个。

求能够获得的最大价值。

每一个物品都会有且只有一个依赖的对象，只有当买下其依赖的对象时，才可以购买这个物品。这就是依赖背包的模型，不同物体之间存在依赖关系。

把盒子看作是一个价格为 $p_i$ 价值为 $0$ 的物品。这样这道题就是一个简化的依赖背包。因为在这道题中，依赖其他物品的物品不会被依赖。于是我们可以把所有的物品按照其所依赖的物品进行分组。

例如 $2,3,4$ 依赖 $1$，$6,7$ 依赖 $5$。那么就可以将物品分为两组，第一组为 $1,2,3,4$，第二组为 $5,6,7$。

在这道题中，题目已经帮我们分好了组，每个盒子就可以当作是一个组来看待。

与分组背包类似，我们以组为单位来进行背包。

容易发现，如果我们买了这个被依赖的物品（也就是盒子），就可以对组内的物品做 01 背包，因为买了盒子之后，这些物品就不会有任何其他的限制，只需要套用 01 背包即可。

于是我们可以以组为单位进行背包，枚举该盒子是否选择来进行 dp 转移。

实现方法

设 $dp[i][j]$ 为在 $1\sim i$ 盒子（组）中进行选择，总钱数为 $j$ 时可以获得的最大价值。

当枚举第 $i$ 个盒子（组）时，盒子的价格为 $p_i$，共有 $m_i$ 个物品：

  1. 首先计算出购买第 $i$ 个盒子时的情况（如果购买该组的物品时，一定要先购买盒子）。状态转移方程为：\(dp[i][j]=\begin{cases} -1& j<p_i\\dp[i - 1][j - p_i]& j\geq p_i \end{cases}\)
  2. 购买完盒子后，枚举 $m_i$ 个物品，第 $k$ 个物品的价格为 $c_k$，价值为 $v_k$，然后进行 01 背包，状态转移方程为：$dp[i][j]=\max(dp[i][j], dp[i - 1][j - c_k] + v_k)$ 其中 $dp[i - 1][j - c_k] \neq -1,c_k \leq j \leq w$。
  3. 接下来将购买和不购买第 $i$ 个盒子（组）时的情况进行合并。状态转移为：$dp[i][j]=\max(dp[i][j], dp[i - 1][j])$ 其中 $0 \leq j \leq w$。

注意：实现的顺序一定要严格按照的步骤进行，否则可能会出现只买了物品，但是没有买盒子的情况。

多层依赖背包

多层依赖背包，也称树形依赖背包。与上一道题中的背包不同，多层依赖背包存在更长的依赖链。即存在：$A$ 依赖 $B$ , $B$ 依赖 $C$ 的情况。

我们用 $A\to B$ 来表示 $A$ 依赖 $B$ ，那么当 $A \to B \to C \to A$ 时，$A,B,C$ 三个物品必须同时选择，所以可以将这三个物品视为同一个物品。所以如果将依赖关系视作边，物品视作点，那么对于任何一张依赖图，我们都可以通过 tarjan 缩点的方式将其转化为树形。（我们会在下一个 Level 学习 tarjan 缩点算法，目前我们只需要知道有方法可以将任意的依赖图转化为树形即可）

为了简洁，接下来我们只考虑依赖关系为树的情况。

例如下面的图:

表示:

显然我们无法用之前的方法来解决这个问题，因为依赖关系变得比上一道题复杂得多。

在这个问题中，我们利用了 dfs 序的性质。

什么是 dfs 序呢？从树根开始进行 dfs 搜索，将所有的点按照其被搜索到的顺序排列到序列中，这样构造出的序列就叫做 dfs 序列。如果点 $i$ 的 dfs 序为 $x$ ，就表示这个点是第 $x$ 个被访问的，在 dfs 序列中的下标为 $x$ 。

设 $f[i][j]$ 表示考虑 dfs 序内 $i$ ~ $n$ 的点，剩余可用的容量为 $j$ 时，所能获得的最多的价值。在转移时，我们可以枚举选择该点与不选择该点两种情况。

所以我们可以写出转移方程：

\[\displaystyle f[i][j] = max(f[i+siz[id_i]][j], f[i+1][j-w[id_i]] + val[id_i])\]

注意我们的 $i$ 表示的是 dfs 序中的下标 ，所以需要通过 $id_i$ 的映射来得到 dfs 序为 $i$ 的点编号。

多重背包的二进制优化

多重背包

背包容量为 $V$。有 $N$ 种物品，第 $i$ 种物品的体积是 $c_i$，价值是 $w_i$，每种物品的数量都是有限的，为 $n_i$。

我们之前学习了解决这个问题的比较朴素的算法：

在转移的过程中枚举 $k$，代表第 $i$ 个物品选取的数量，和 01 背包的思想一样，有如下转移。

\[\displaystyle \displaystyle dp[i][v] = max(dp[i][v], dp[i-1][v-k\*c_i] + k\*w_i), 0 \leq k \leq n_i\]

时间复杂度为 $\mathcal{O}(V\sum n)$。

这一节，我们学习一个更为高效的算法来解决多重背包。

二进制优化

我们发现，用 $1, 2, 4, 8, 16, 32$ 实际上可以组成 $1$ 到 $63$ 上的任意整数。由于所有数都是 $2$ 的幂次，每个数都对应一个二进制位。所以每一个二进制位都可以选或者不选，所以 $1$ 到 $63$ 上每个数都能组成。

利用这个特征，假设第 $i$ 个物品有 $n_i$ 件，我们把它分成若干组，每一组个数分别为 $1, 2, 4, \cdots, 2^{k-1}$, $n_i - 2^k + 1$，其中 $k$ 是满足 $n_i - 2^k + 1 > 0$ 的最大整数。而每一组物品对应的体积和价值分别为 $(c_i,w_i)$, $(2c_i,2w_i),(4c_i,4w_i), \cdots, (2^{k-1}c_i, 2^{k-1}w_i)$, $((n_i - 2^k + 1)c_i, (n_i - 2^k + 1)w_i)$。

可以发现，通过组合这些物品，我们可以组成 $1$ 到 $n$ 上的任意数，而且也只能组合出 $1$ 到 $n$ 之间的数。所以我们就可以将原问题等价转化为对拆分后形成的物品进行 01 背包。

$n$ 件物品，就拆分成至多 $\log n$ 件物品，再转化为 01 背包问题求解，原问题复杂度降低到 $\mathcal{O}(V\sum \log n)$。

核心代码：

int ncnt = 0;
// 二进制拆分
for (int i = 1; i <= N; ++i) {
    int k;
    // 找到最大的 k
    for (k = 1; n[i] - (1 << k) + 1 > 0; ++k) {
        nc[ncnt] = (1 << (k - 1)) * c[i];
        nw[ncnt] = (1 << (k - 1)) * w[i];
        ++ncnt;
    }
    --k;
    // 最后一组
    nc[ncnt] = (n[i] - (1 << k) + 1) * c[i];
    nw[ncnt] = (n[i] - (1 << k) + 1) * w[i];
    ++ncnt;
}
// 01 背包
for (int i = 0; i < ncnt; ++i) {
    for (int j = V; j >= nc[i]; --j) {
        dp[j] = max(dp[j], dp[j - nc[i]] + nw[i]);
    }
}

动态规划综合

单调栈

我们一起看一道题目。

给一个长度为 $n$ 的数组 $A$ 和一个长度 $k$，你需要从前到后输出每个长度为 $k$ 的区间内的最小值和最大值。

例如：$k = 3,n = 5$，数组 $a$ 为 ${1,3,-1,-3,5}$。

  1. 第一个长度为 $k$ 的区间：$[1,3,-1]$，最大值为 $3$，最小值为 $-1$。
  2. 第二个长度为 $k$ 的区间：$[3,-1,-3]$，最大值 $3$，最小值为 $-3$。
  3. 第三个长度为 $k$ 的区间：$[-1,-3,5]$ 最大值 $5$，最小值 $-3$。

知道了题意之后，我们来思考一下，这个题应该如何处理。

最直观的想法是，每遍历到一个新的数值，就将当前 $k$ 大小的窗口重新寻找一个最小值和最大值。

for (int i = 0; i < n - k + 1; i++) {
    int mx = -0x3f3f3f3f;     //最大值
    int mn = 0x3f3f3f3f;      //最小值
    for (int j = i; j < i + k; j++) {
        mx = max(mx, a[j]);
        mn = min(mn, a[j]);
    }
    cout << mx << " " << mn << endl;
}

时间复杂度为：$\mathcal{O}(nk)$。

我们回到最开始的例子：$k = 3,n = 5$，数组 $a$ 为 ${1,3,-1,-3,5}$。

实际上我们会发现，扫描到 $a_2 = 3$ 时，$a_1 = 1$ 就再不可能成为某个子段的最大值了；而扫描到 $a_3 = -1$ 时，$a_2 = 3$ 就再不可能成为某个子段的最小值了。

如果将结论一般化，当我们扫描到 $a_i$ 时，对于每个 $j>i$，有：

  1. $a_i>a_j$，那么 $a_j$ 将不可能再作为以第 $i,i+1,\cdots,n$ 个元素结尾的任意 连续子段 的 最大值。

  2. $a_i<a_j$，那么 $a_j$ 将不可能再作为以第 $i,i+1,\cdots,n$ 个元素结尾的任意 连续子段 的 最小值。

所以我们需要一个数据结构，这个数据结构需要维护的是：当扫描到 $a_i$​ 时，还有可能作为以第 $i$ 个元素为结尾的某一个 连续子段 的 最大/小值 的元素。

以维护最小值为例：

我们可以发现，维护的元素是单调有序的。

实际上我们可以使用一个栈来维护。我们以维护最小值为例：

stack<int> T;
for (int i = 0; i < n; i++) {
    cin >> a[i];
    while (!T.empty() && T.top() >= a[i]) { // 把栈里面值大于等于 a[i] 的数全部剔除
        T.pop();
    }
    T.push(a[i]);
}

以 $k = 3,n = 5$，数组 $a$ 为 ${1,3,-1,-3,5}$ 为例：

实际上，上述结论是在 $a_i$ 是一定可能成为结尾为 $a_i$ 的连续子段的最小值（长度为 $1$ 的子段）的前提下进行的。而且我们会发现栈内的元素由栈顶到栈底是单调递减的，这是因为先入栈的元素在原序列内靠前，如果存在深度较大的元素大于深度较低的元素，就不满足上一页所讲的性质了。

那么我们便称这样的数据结构为 单调栈，因为栈内深度从浅到深一定是单调递增/递减的。

接下来我们来看看算法的时间复杂度。实际上我们会发现，对于数列里面的每一个元素而言，它入/出栈都最多有一次，所以整体的时间复杂度是 $O(n)$。

单调队列

刚才我们已经将时间复杂度进行了改善，但是有一个问题我们还没有解决：

连续子段的长度不能超过 $k$。

实际上我们用单调栈已经不能解决这个问题了，因为我们不能从栈底删除元素，但是我们学过了双端队列，它是可以从队列的头尾删除元素的。

所以我们来思考一下如何用双端队列来解决这个问题，在这里我们以解决子段最小值为例。

我们需要一个数据结构，这个数据结构需要维护的是扫描到 $a_i$ 时，还有可能作为以第 $i$ 个元素为结尾的某一个 长度不大于 $k$ 的 连续子段 的 最小值 的元素。

由于我们添加了 长度不大于 $k$ 这个条件，所以我们需要将数列内元素的下标作为双端队列中的元素了。然后队列中从队首到队尾，下标和在数列中对应的值都是单调递增的。

当扫描到 $a_i$ 的时候，首先需要将单调队列中下标小于等于 $i-k$ 的元素删除，因为这些元素已经不可能成为以第 $i$ 个元素为结尾的某一个 长度不大于 $k$ 的 连续子段 的一部分：

while (!T.empty() && T.front() <= i - k) {
    T.pop_front();
}

然后我们再去满足单调队列中元素在数列中对应的值的单调性：

while (!T.empty() && a[T.back()] >= a[i]) {
    T.pop_back();
}

最后我们把 $i$ 加入到单调队列：

T.push_back(i);

当然，你需要从队尾加入。当这些操作完成了之后，你便可以知道以 $a_i$ 结尾的长度不大于 $k$ 的所有连续子段的元素最小值。队首元素在数列中对应的值就是这个最小值。

实际上，无论是单调栈还是单调队列，它们其实都是用于优化某些具有一定单调性的问题的。往后你还会学习到一些对于动态规划问题的优化方式，它们也同样利用了这种思想。

组建队伍

你需要组建一支排球队。为了组建这个排球队，你需要从 $n$ 个人中选出 $p$ 个人，并且分配到队伍里的 $p$ 个不同的位置，且每个位置上都恰好有一个人。另外还需要从剩下的人中选出恰好 $q$ 个人作为观众。

对于第 $i$ 个人，已知他作为观众时能增加 $a_i$ 点力量，还有他作为队员在队伍的第 $j$ 个位置上时能为队伍增加 $s_{i,j}$ 点力量。请问这只排球队力量的最大值是多少？

输入格式

第一行包含 $3$ 个整数 $n,p,k$。($2\le q \leq n\leq 10^5,1\leq p\leq 7,1\leq k,p+k\leq n$)。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。 ($1\leq a_i\leq 10^9$)。

接下来 $n$ 行的第 $i$ 行包含 $p$ 个整数 $s_{i,1},s_{i,2},\cdots ,s_{i,p}$。 ($1\leq s_{i,j}\leq 10^9$)

输出格式

输出一个整数 $res$ 表示这只排球队力量的最大值。

输入样例

6 2 3
78 93 9 17 13 78
80 97
30 52
26 17
56 68
60 36
84 55

输出样例

377

每个人在每个位置上的力量可能都不相同，由此我们需要具体记录下有哪些位置已经被占用，由于 $p$ 很小，所以我们可以用状态压缩的方式记录。

由此我们可以得到一个最朴素的状态表示：

$dp_{i,j,k}$，即安排了前 $i$ 个人之后，排球队的安排状态是 $j$，被安排为观众的人数为 $k$ 时，力量的最大值。

那么对于每一个人，我们可以决定：

然后就可以得到状态转移方程。

但是问题来了：状态个数的复杂度为 $O(nq2^p)$，很明显是无法接受的。

需要考虑如何优化状态。

如果我们现在只需要选出恰好 $k$ 个人作为观众，那么一个很明显的贪心策略就是按照 $a_i$ 的大小从大到小进行选择。

我们将所有的人按照它 $a_i$ 从大到小进行排序，然后依次判断每个人扮演的角色。由刚才的贪心策略可以得知，如果这个人不会被选入队伍，那么这个人一定会被选为观众（除非观众数量已满）。

所以我们只用在意一个人是否会被选入队伍，以及这个人在队伍中是什么位置。注意到队伍中的位置至多只有 $7$ 个，所以我们可以考虑将这 $7$ 个位置进行状态压缩。

设 $f[i][S]$ 表示已经分配好 $1$ ~ $i$ 的人，队伍不同位置的占用情况为 $S$ 。其中 $S$ 是对队伍位置的状态压缩，如果某一位为 $1$ ，则表示对应位置已经分配了人。

由贪心的策略可知， $f[i][S]$ 表示的状态内，已经选出了 $\min{i - S , k}$ 个人作为观众（其中 $ S $ 表示 $S$ 内 $1$ 的个数）。

所以我们可以按照 $a_i$ 从大到小依次枚举每个人，然后分别枚举每个人作为队员以及不做队员的情况来进行转移。

找出最短路

给定一张 $n$ 个点， $m$ 条边的无向连通图，所有边的长度都为 $1$ 。一共有两种边：完好无损的边和需要维修的边。现在我们需要找到一条从 $1$ 到 $n$ 的最短路，然后将在这条最短路上需要维修的边进行维修，并且毁掉所有不在这条最短路上的所有完好无损的边。

我们将：在这条路径上的需要维修的边的数量 $+$ 不在这条路径上的完好无损的边的数量 定义为这条路径的影响值。

现在需要找出影响最小的最短路，并输出其影响值。

输入格式

第一行输入两个整数 $n,m(2 \le n,m \le 10^5)$ 表示点的数量和边的数量。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条无向边 $(u,v)$，如果：

输出格式

输出一个整数，表示影响最小的最短路的影响值。

输入样例

9 10
1 2 0
2 3 0
1 4 1
4 5 1
4 6 1
6 7 1
1 7 0
1 8 0
7 8 0
9 7 1

输出样例

5

样例解释

这道题目需要我们将最短路算法与动态规划结合起来，我们假设 $d_u$ 表示从 $1$ 到 $u$ 的最短路径，因为每条边的长度为 $1$，所以 $d_u$ 也表示从 $1$ 到 $u$ 的最短路径上的边的数量。

所以我们可以得知：从 $1$ 到 $n$ 的最短路上有 $d_n$ 条边，假设我们知道这条最短路中完好无损的边的数量为 $x$ ，那么这条最短路中需要维修的边的数量就为 $d_n - x$ 。设图中共含有 $sum$ 条完好无损的边，那么不在这条最短路中的完好无损的边的数量即为 $sum - x$ 。

所以我们可以得知，这条最短路的影响为： $(d_n - x) + (sum - x)$ ，即 $sum + d_n - 2x$ 。 所以实际上我们需要找的是包含完好的边最多的最短路。

所以这实际上是一个在最短路中的动态规划，我们可以用 $f_u$ 表示从 $1$ 开始通过最短路到达 $u$ 时，路上所经过的完好无损的边的最大数量。

也就是可以得到转移方程： $f_u = \max_{(v,u)\in \text{最短路}}{f_v+w(v,u)}$ ，其中 $w(v,u)$ 表示的是 $(v,u)$ 这条边的状态，如果 $w(v,u) = 1$ 则表示该边是完好无损的边。

选择数字

给定 $n$ 个正整数 $a_i$ ，求最少选出多少个 $a_i$ 使得他们的最大公约数为 $1$ 。

输入格式

第一行一个整数 $n$，表示整数的个数。

第二行 $n$ 个以空格隔开的正整数 $a_i$。

数据范围：$1\le n,a_i\le 3\times10^5$

输出格式

输出一个整数，表示答案。

无解情况输出 $-1$ 。

输入样例

3
10 6 15

输出样例

3

我们设状态 $f[i][j]$ 表示取出 $i$ 个数，此时最大公约数为 $j$ 的方案数。如果 $f[i][1]$ 的值为 $0$ ，就表示不存在选出 $i$ 个数使他们最大公约数为 $1$ 的方案。

那么我们这个状态该如何转移呢？

我们设 $cnt_i$ 表示这 $n$ 个正整数中有多少个数可以被 $i$ 整除。

例如对于正整数：[2,4,6,9,10]，$cnt_2 = 4, cnt_3 = 2$。

随后我们可以应用一个简单的容斥原理得到方程：$f[i][j] = {cnt[j]\choose i} - \sum_{k=2}f[i][j\times k]$

其中的 ${cnt[j]\choose i}$ 表示的是从所有是 $j$ 的倍数的数字中取出 $i$ 个的方案数，那么这些方案就可能包括最大公约数为 $j,2j,3j,\cdots$ 的情况。因为我们只需要保留最大公约数为 $j$ 的方案，所以我们需要减去最大公约数为 $2j,3j,\cdots$ 的方案，即减去 $\sum_{k=2}f[i][j\times k]$ 。

但是我们计算一下，现在的时间复杂度是 $O(n\times \max{a_i})$，不足以通过这道题，该如何解决这个问题呢？

其实答案不会超过 $7$，也就是说 最多只需要计算到 $f[7][1]$，不需要再计算之后的状态。

因为一些数的最大公约数的实质是保留这些数公共质因子，所以如果有 $7$ 个数字的公约数为 $1$，并且找不到更小的取数字方法使得公约数为 $1$，那么此时每个数字都会有且仅有 $6$ 个质因子，并且缺少一个一定会被剩下的所有数字拥有的质因子。

我们可以用 $3$ 来举例，如果有 $3$ 个数字的公约数为 $1$，并且找不到更小的取数字方法使得公约数为 $1$。那么此时这三个数字应该分别为：$[2\times3, 2\times5, 3\times5]$。

为什么一定是只能有 $7$ 个呢？

因为最小的 $7$ 个质数的乘积大于题目中给定的范围 $3\times10^5$，所以每个数最多只能包含 $6$ 个质因子。因此答案不会超过 $7$，如果 $f[7][1]$ 仍然是 $0$，那么这组数据无解。

所以这部分的复杂度为 $O(\max{a_i})$，是可以通过这道题的。

dp 与其他算法的搭配

回顾我们本节所解决的四个题，在使用动态规划进行转移的同时，还使用了贪心、最短路和容斥等算法。利用贪心算法来对转移与状态设计进行优化，利用最短路来规定动态规划转移的路径，利用容斥来计算动态规划转移的方式。

其实有很多算法可以和动态规划相结合，这里提到的三种不过是较为常见的三种算法。

当然，动态规划算法与其他算法的搭配也是非常常见的。除了用算法来计算动态规划的转移，也有很多时候会使用一些数据结构优化来降低动态规划转移的复杂度。

例如对于动态规划转移方程：$f_i = \min_{j < i\text{且}a_j<a_i}{f_j}$

我们就可以通过在值域中维护最小值的方式，来使每一次转移的复杂度降低到 $O(\log n)$，不然我们每次都需要从 $1$ 到 $i-1$ 遍历来进行转移，复杂度为 $O(n^2)$ 。

这里在值域中维护最小值的方式我们选择用 线段树 或 树状数组 来进行维护。