0x01|算法竞赛进阶指南 - 位运算3题详解
算法进阶指南看了开头一部分，个人感觉讲解的比较透彻，于是打算写一些个人的读书笔记，主要是做题后做一个总结，不求快，但求能一点点讲清楚每个知识点。这一节来看看第一章的位运算部分。
算法进阶指南的的题目都在AcWing上面，这里就按照AcWing上的题号来写题目编号。
题目89、求 a 的 b 次方对 p 取模的值。
「题意：」
如题，就是求
。
这道题也是快速幂模板，作为书中的第一道例题，有必要重新看一下快速幂的原理。
比如求
，这里a是3，b是13，p是100。
如果我们直接用乘法，那么就是
对于b非常大（比如10的9次方）的情况，效率会很低。快速幂能很好的解决这个问题。
快速幂可以理解为二进制幂，将b转换为二进制格式，比如13的二进制就是8+4+1 => 1000 ^ 0100 ^ 0001 => 1101
也就是：
如果从b的二进制末位开始遍历i（i从0开始）到最左边，凡是遇到1，那么就会将
作为一项乘到结果中。
从乘式右边开始，每一项都是前一项的平方。
「C++代码如下：」
#include <iostream>
using namespace std;
int main()
{
long long a, b, p;
scanf("%ld%ld%ld", &a, &b, &p);
long long res = 1;
while (b)
{
// b二进制中的1，表示这次可以将当前a的迭代值作为一项乘到res中
if (b & 1)
res = res * a % p;
// b每次都会右移一位，每次我们都是处理最末位的二进制值
b >>= 1; //b右移了一位后,a也需要更新
// 迭代a，a在这里其实是每次的迭代值,等于a^{2^i}，其中i从0开始
a = a * a % p;
}
printf("%ld\n", res % p);
return 0;
}
题目90、64位整数乘法
「题意：」
求 a 乘 b 对 p 取模的值。
「数据范围：」
这里直接相乘显然会超过64位，还是快速幂，上面我们对快速幂有了大概的理解，再来看下这题的变化。
举个栗子，对于
用快速幂怎么做呢？
我们还是对b进行二进制处理，那么：
也就是
从最右边开始，每一项都是前一项的2倍，参考题目89的代码，
「代码：」
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
int main()
{
ll a, b, p, res;
cin >> a >> b >> p;
res = 0;
while (b)
{
// 只有位为1的部分加入到res中
if (b & 1)
res = (res + a) % p;
// b右移一位
b >>= 1;
// 每一项都是前一项的2倍
a = 2 * a % p;
}
cout << res << endl;
return 0;
}
题目3、最短Hamilton路径
「题意：」
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
「解题思路：」
这道题暴力解法就是搜索，看最终哪条路径的总值最小，但是复杂度非常高，肯定会超时。
这道题不再是像上面2题可以用快速幂解决，而是需要动态规划来解决，采用位的方式存储状态。
动态规划思路：首先需要思考状态方程，在任意时刻，如何表示哪些点走过，哪些点没走过呢？显然可以用一个n位的二进制数。若第i位位1，就表示第i个点走过了。
在任意时刻，还需要知道当前在那个点，所以可以用
来表示状态，
中的i表示点经过的状态，j表示到了那个点。
目标值是
，比如n为3，那么(1<<n)-1恰好为7（二进制为111），表示所有点都经过了。
那么状态方程呢？
在任意时刻，有公式
这里
除掉
之后的状态
注意这里
可以是0到
，
会遍历k取最小值。
来看代码：
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 20, M = 1<<20;
// 这里f占用空间非常大，不能开在main函数中，全局变量是在堆中开空间
int f[M][N], weight[N][N];
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>weight[i][j];
}
}
// 初始化最大值
memset(f, 0x3f, sizeof(f));
// i为00...01表示在经过位置0
// j为0表示目前处于位置0
f[1][0] = 0;
for(int i=0; i<1<<n; i++){
for(int j=0; j<n; j++){
if(i>>j & 1){
for(int k=0; k<n; k++){
// i-(1<<j)作用是去掉j位的1
// i-(1<<j) >> k & 1在位置k为1（经过k）
if(i-(1<<j) >> k & 1){
f[i][j] = min(f[i][j], f[i-(1<<j)][k]+weight[k][j]);
}
}
}
}
}
cout<<f[(1<<n)-1][n-1]<<endl;
return 0;
}
这里还要注意的是位的优先级，位操作的优先级都比较低，如果不确定可以都用括号，防止优先级错误。这道题需要记住位移操作的优先级低于加减的优先级，需要括起来才行。
本题中
还可以使用i ^ (1<<j)来写，异或操作是啥，异或就是不同的就是1，所以称为异，这里i中j位为1，异或肯定为0，所以效果是一样的，不过前者可能更好理解一点，直接减去也是0，后者可能性能更好。（前者是yxc的视频中的写法，后者是李煜东的算法书上的写法）
然后就是f的空间占用比较大，放在全局里面用堆内存进行分配，切记~
总结
以上3题就是算法进阶指南里面的入门题目啦，新手学习的时候多思考，因为快速幂和状态压缩的理解都需要一点时间。快速幂能够应用在指数运算和乘法运算中，其实就是对二进制进行分解处理，每一项都是一次迭代的结果，从最小的项开始运算，每次运算都依赖上次的运算，最终只需要log(n)复杂度完成运算。
状态压缩后面在动态规划的习题中再着重讲解，本题也是一个很典型的题目，关键是确定DP方程的影响因素，题目3中主要是当前点的状态和当前位置2个因素可以涵盖所有情况，状态转移需要进行位运算，主要是对某位进行赋值和取值操作，多练习就能够熟悉使用了。
如果还有不懂的，可以留言给我再讲解，也可以参考《算法竞赛进阶指南》，还可以参考AcWing的yxc的视频教程，相对来说视频教程更容易理解。
原创不易，如果看了这篇能够提高你对位运算的理解，请点个赞哦。
