快速幂笔记

快速幂

描述

快速幂算法的核心思想是每一步都把指数分成两半，相应的底数做平方运算，这样就能将指数不断变小，同时循环次数降低，结果相同。

例如 \(a^{11}=a^{2^0+2^1+2^2}\)

很自然可以得到递归方程： \[ a^n=\begin{cases} a^{n-1}\cdot a,\mathrm{if\ n\ is\ odd}\\ a^{\frac n2}\cdot a^{\frac n2},\mathrm{if\ n\ is\ even\ but\ not\ 0}\\ 1,\mathrm{if\ n=0} \end{cases} \]

C++ 实现

// 计算 base^exp
template<typename Type>
Type fastPower(Type base, unsigned int exp)
{
	Type result(base);
	while (exp)
	{
		if (exp & 1)result = result * base;
		base *= base;
		exp >>= 1;
	}
	return result;
}

// 计算 base^exp%mod
template<typename Type>
Type fastPower(Type base, unsigned int exp, unsigned int mod)
{
	Type result(base);
	while (exp)
	{
		if (exp & 1)result = result * base % mod;
		base = base * base % mod;
		exp >>= 1;
	}
	return result;
}

矩阵快速幂

特别地，实际上对于矩阵来说，也可以按照同样的道理进行快速幂计算。

因为矩阵也满足线性运算，自然可以进行快速幂。例如 \[ \left(\left[ \begin{matrix} 1&2\\ 3&4 \end{matrix} \right]\right)^{11} = \displaystyle\left(\left[ \begin{matrix} 1&2\\ 3&4 \end{matrix} \right]\right)^{2^0+2^1+2^2} \]

应用

矩阵加速递推

矩阵快速幂可以应用在加速递推上。

例如对于斐波那契数列 \(f(n)=f(n-1)+f(n-2)\)，当 \(n\) 较小时，我们可以通过递归或者循环得到数列值；但当 \(n\) 较大时，使用递归或者循环效率就低了；当 \(n\) 特别大时，不难发现如果用普通的算法几乎已经是无解了。

但是，我们可以用另一种方法解决递推数列问题。

我们构建一个 \(1\times2\) 的答案矩阵 \(F(n)\)： \[ F(n)=\left[\begin{matrix}f(n)&f(n-1)\end{matrix}\right] \] 然后构造一个 \(2\times2\) 的累乘矩阵 \(base\)： \[ base=\left[\begin{matrix}a&b\\c&d\end{matrix}\right] \] 其中 \(a,b,c,d\) 均为未知数，需要我们构造后能够满足条件： \[ F(n)\times base=F(n+1)=\left[\begin{matrix}f(n+1)&f(n)\end{matrix}\right] \] 即 \[ \left[\begin{matrix}f(n)&f(n-1)\end{matrix}\right]\times \left[\begin{matrix}a&b\\c&d\end{matrix}\right]=\left[\begin{matrix}af(n)+cf(n-1)&bf(n)+df(n-1)\end{matrix}\right]=\left[\begin{matrix}f(n+1)&f(n)\end{matrix}\right] \] 可以推得累乘矩阵 \(base\) 为 \[ base=\left[\begin{matrix}1&1\\1&0\end{matrix}\right] \] 那么我们就能够将斐波那契数列递推公式转换为含有矩阵的公式： \[ F(n+k)=F(n)\times base^k \] 比如说我们取 \(n=2\)，即 \(F(n)=\left[\begin{matrix}f(2)&f(1)\end{matrix}\right]=\left[\begin{matrix}1&1\end{matrix}\right]\)

那么我们要求 \(F(20)\)，即为 \[ F(20)=F(2)*base^{18} \] 通过矩阵快速幂我们可以快速得到 \(base^{18}\) 的结果，最后再与 \(F(2)\) 矩阵相乘即可得到最终结果，将算法效率提高至 \(O(log\ n)\)

带常数项 \(k\)

例如递推方程 \(f(n)=f(n-1)+f(n-2)+k\)，求 \(f(n)\)

构建常数项递推式：\(k_n=k_{n-1}+0\)

常数项不可忽略，需要专门加一维来计算常数。

故构建矩阵如下： \[ F(n)=\left[\begin{matrix}f(n)&f(n-1)&k\end{matrix}\right],\ base=\left[\begin{matrix}1&1&0\\1&0&0\\1&0&1\end{matrix}\right] \]

带未知数项 \(n\)

例如递推方程 \(f(n)=f(n-1)+f(n-2)+n\)，求 \(f(n)\)

构建常数项递推式：\(n=(n-1)+1\)

虽然 \(f(n)\) 的转移只有四项，但需要加多一维来辅助未知项 \(n\) 的递推。

故构建矩阵如下： \[ F(n)=\left[\begin{matrix}f(n)&f(n-1)&n&1\end{matrix}\right],\ base=\left[\begin{matrix}1&1&0&0\\1&0&0&0\\1&0&1&0\\1&0&1&1\end{matrix}\right] \]

求和

例如递推方程 \(f(n)=f(n-1)+f(n-2)\)，求 \(S(n)=\displaystyle\sum_{i=1}^nf(i)\)

需要尝试将 \(S(n)\) 放入矩阵与 \(f(n)\) 一起递推。

前缀和的递推式为：\(S(n)=S(n-1)+f(n)\)

故构建矩阵如下： \[ F(n)=\left[\begin{matrix}f(n)&f(n-1)&S(n-1)\end{matrix}\right],\ base=\left[\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}\right] \]