black_trees 的重来之路-part1：

这是lyd的蓝书的扫题计划。

共 323 题，预计在8个月之内扫完 80%。

我会单独新建一个文件夹，把所有我重来的代码都放进去。

在做完每个章节之后会有归档，进度可以在 Github 上查看。

0x00「基本算法」例题

CH0101 a^b

这是快速幂的板子题，让你求 \(a^b \% p\) 的值。

首先有一个非常重要的二进制拆分思想：

对于 $\forall x \in \mathbb{N}^* $ ，可以把 \(x\) 的二进制表示写成如下形式 :

\(c_1\times 2^{0} + c_2\times 2^{1} + ... + c_k\times 2^{k-1}\)。

其中 \(c_i\) 表示 \(x\) 在二进制下的第 \(i\) 位（从 \(1\) 开始）的数字是多少。

然后我们考虑把 \(b\) 这样子拆分。

实现只需要每次把 \(b\) 的最低位 \(i\) 取出来，如果为 \(1\) 那么就把 \(a^{2^{i-1}}\) 乘到答案里面，就能算出 \(a^b\)。

\(a\) 可以利用 \(a^{2^{k}}=(a^{2^{k-1}})^2\) 这个式子来递推处理。

记住答案最开始要设置成 \(1\) 对 \(p\) 取模以避免 \(p=1\) 的时候答案出错。

CH0102 64位整数乘法

考虑把 \(b\) 像上一题一样拆分，那么每次令 \(a=2a\) ，如果 \(b\) 的当前最低位是 \(1\) 那么累加答案。

POJ1995 Raising Modulo Numbers

依旧是快速幂的模板题。

只需要分别求个快速幂然后全部加起来即可。

不要忘记加的时候取模。

CH0103 最短Hamilton路径

状压 DP 的模板题。

我们设 \(f_msk\) 表示走到的点集合为 \(msk\) 的时候的最短路径。

但是发现这样子没法表示状态，所以再加一维，\(f_{msk,i}\) 表示表示走到的点集合为 \(msk\) ，且当前在 \(i\) 的时候的最短路径。

那么先枚举状态，然后枚举所有点对来转移即可。

CH0104 [NOI2014] 起床困难综合症

很精妙。

我们发现如果直接去找这个数是什么会特别麻烦。

不妨换个思路，因为位运算的特点之一就是不进位（比如异或就是二进制下的不进位加法）。

所以每一位之间不会干扰。

我们考虑枚举答案的每一个数位到底是 \(0\) 还是 \(1\)。

然后对于每个位置，我们取出每一扇门上数字在二进制下的这一位进行运算。

如果这一位选 \(0\) 只需要记录当前的攻击力最大值即可，选 \(1\) ，那么还需要累加答案。

复杂度在 \(\log\) 级别。

不过我不是很明白，为什么我的Code里面，如果枚举的这个答案的位数是 \(30,29\) 位才能过。

\(32,31,28\) 都或多或少会挂一两个点呢？