位运算

a^b

算法：快速幂。

考虑一些经典的分类讨论：

• $b$ 为奇数，此时分解为 $a^{\frac{b-1}{2}}\times a^{\frac{b-1}{2}}\times a$。

• $b$ 为偶数，此时分解为 $a^{\frac{b}{2}}\times a^{\frac{b}{2}}$。

我们的边界为 $a$，因为这是已经给出的。

所以我们发现，每次 $b$ 会减少一半，时间复杂度 $O(log b)$，在 $b\le 10^9$ 时可以轻松通过。

增加模数

算法：快速幂。

先考虑暴力枚举，$b_i$ 的极限是 $10^7$，所以我们要进行 $4.5\times 10^{13}$ 次运算，这是一定会超时的，所以考虑优化。

发现 $b_i$ 数据范围很大，于是考虑用快速幂优化，对于 $a_i^{b_i}$ 这样的式子可以快速计算，这样时间复杂度是 $O(Tmlog b)$，可以通过。

64位整数乘法

算法：龟速乘。

发现 $a\times b$ 显然会爆 $long$ $long$，所以我们有 $2$ 种方案：

• 使用高精度，但这样不够优美。

• 使用龟速乘。

我们可以把 $a$ 加上 $b$ 次，比较显然地，$b$ 可以被拆成一个二进制数，我们把二进制是 $1$ 的位加上即可。

具体地，每次把当前的数乘 $2$，判断 $b$ 的二进制表示中第 $i$ 位是不是 $1$，如果是 $1$，答案加上 $2^i\times a$，这里可以每次把 $a$ 乘 $2$ 并取模，就不会爆掉了。

时间复杂度 $O(log b)$，可以轻松通过。

最短Hamilton路径

算法：状态压缩，动态规划。

这里先提出一种新的动态规划分析方式：

我们把一个状态看作一个集合，既然是集合，里面就有元素，我们根据题目的要求把这个状态的数组记为这个集合的一个特殊值(例如：最大值，最小值，总和，数量之类的)，就是属性。

接下来分析一下状态，$f_{i,j}$ 表示所有从 $0$ 走到 $j$，走过点的二进制表示为 $i$ 的路程的最小值。

然后想一想怎么转移，我们可以枚举 $j$ 的上一个点记为 $k$，所以 $f_{i,j}$ 可以由 $f_{i-2^j,k} + a_{k,j}$ 转移而来，即转移方程为 $f_{i,j}=\min(f_{i,j},f_{i-2^j,k} + a_{k,j})$。

起床困难综合症

算法：位运算。