Binary Lifting

Published: by Creative Commons Licence

  • Tags:

快速幂技术

快速幂技术是一种非常高效且简单的优化技术。对于环$U$上的某个元素$x$,我们要求$x^n$,我们可以用快速幂技术仅用$O(\log_2n)$次乘法运算即可高效完成这个过程。

快速幂的原理如下:

\[\left\{ \begin{array}{lclr} x^n&=&(x^{\frac{n}{2}})^2 &,2\mid n\\ x^n&=&(x^{\frac{n-1}{2}})^2\cdot x &,else \end{array} \right.\]

即根据$n$的奇偶性走两套逻辑。定义$T(n)$表示指数为$n$所需要执行的运算次数,可以发现$T(n)=T(n/2)+O(1)$,因此有$T(n)=O(\log_2n)$。

快速幂能适用于一切满足结合律的运算,不仅限于乘法运算。下面给出一些例题:

题目1:要求仅用加法以及位运算计算两个整数的乘积$a\cdot b$。

可以发现$a\cdot b=\sum_{i=1}^ba$,而加法也是满足结合律的,因此可以用快速幂来优化。

题目2:计算斐波那契数列的第$10^{18}$项的后四位数字。

由于斐波那契是线性递推数列,因此我们可以用矩阵来表示递推关系。而矩阵的乘法运算是满足结合律的。

题目3:有$n$个石头($n\leq 10^9$),两个人进行比赛,每个人每次可以拿走$a_1,a_2,\ldots,a_m$块石头,这里$a_1,\ldots,a_m\leq 20$且一定包含$1$。拿走最后一块石头的人为输家。问在最优决策的情况下,哪一方一定会获胜。

可以用DP计算,但是$n$太大了。我们发现每个状态都仅有最多前面$20$个状态所完全决定,因此我们可以定义一个函数$f:Z_2^{20}\rightarrow Z_2^{20}$,暴力算出前20个状态,其向量形式记作$s$,而我们要计算的实际上是$f^{n-19}(s)$。由于函数的复合满足结合律,因此可以用快速幂加速。每次函数复合的时间复杂度为$O(2^{20})$,总的时间复杂度为$O(20+2^{20}\log_2n)$。

倍增技术

TODO

状态机和倍增

有一类问题,给定$n$个状态,以及$m$条边,每条边的格式为$(a,b,w(a,b))$表示从状态$a$转移到状态$b$的收益为$w(a,b)$。之后要求计算进行不超过$k$次转移的最大收益,且初始状态为$1$。其中$1\leq k\leq 10^{18}$。

这类问题的核心是定义一个函数$f^t(x,y)$表示从$x$到$y$进行不超过$t$次转移的最大收益。可以发现$f^1(x,y)=w(x,y)$。之后我们可发现$f^t(x,y)=\max_{z} f^i(x,z)+f^{t-i}(z,y)$。如果我们将$f^t$视作一个矩阵,可以发现$f^t$的计算规则很类似于矩阵的乘法规则。如果已知$f^t$,那么我们可以$O(n^3)$计算$f^{t+1}$和$f^{2t}$。

因此我们可以套上快速幂,就可以计算出$f^{k}$,之后我们找到$\max_j f^{k}(1,j)$即可。

题目1:给定一个有向连通图$G=(V,E)$,要求计算所有包含不超过$k$条边的路径中最长的一条路径的长度,其中$1\leq V\leq 1000, V-1\leq E\leq V^2,1\leq k\leq 10^{18}$。

直接使用上面提到的技术就可以求解。