Binary Lifting

Published: by Creative Commons Licence

  • Tags:

快速幂技术

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

快速幂的原理如下:

即根据$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