算法笔记 -- 矩阵快速幂

快速幂

要说矩阵快速幂,那么就得先知道快速幂是什么?

快速幂是数论中一种比较常用的求幂的算法.

普通的求x ^ n问题,需要迭代n次,才可以得到结果,在求解一些比较大的幂次时往往容易超时。

而如果使用快速幂,则可以在O(lgn)时间复杂度内求解出诸如X ^ n这样的问题,底层原理是基于二进制;

比如我们此时需要求解\(a ^ {156_\text{(10)}}\) => \(a^{10011100_\text{(2)}}\)

那么:

如果按照这个方式来求解\(a ^ {156}\),原来需要进行156-1即155次运算的,现在只需要进行这个**指数它的二进制长度*二进制中1个个数**=>8 * 4=24次;

即等于幂次的各个分量之和的二进制位权幂次相乘。

int fastpow(int base,int n,int mod) {
	int ans = 1;
	while(n != 0) {
		if((n & 1) != 0) {
            ans *= (base % mod);
        }
        base *= base;
		n >>= 1;
	}
	return ans % mod;
}

int fastpow(int base,int n) {
	int ans = 1;
	while(n != 0) {
		if((n & 1) != 0) {
            ans *= base;
        }
        base *= base;
		n >>= 1;
	}
	return ans;
}

对于求 \(n\)次幂，我们对 \(n\) 二进制化，当二进制位上为1时，就相乘。

相对而言，快速幂实在是简单不过来，所以很少有直接考快速幂的题。

而对快速幂的应用大多是在其他比较复杂的算法中充当某个环节的组成,比如矩阵快速幂;

矩阵快速幂

一开始接触矩阵快速幂的时候，我还完全不清楚矩阵的运算到底是怎么一回事儿，之前高中也没有接触过线代方面的知识。在刷了数篇博客后总算对矩阵的运算有了一些了解,在这里记录一下;

相对于一般的快速幂，矩阵快速幂仅仅是把他的底数和乘数换成了矩阵形式，而相应的乘法运算什么的也遵循矩阵的运算法则。对于矩阵的基本运算这里也不在多做赘述。

矩阵快速幂主要是用于求一个很复杂的递推式的某一项问题,比如常见的斐波那契数列问题。

斐波那契数列问题一般比较简单,求解范围不大时可以使用动态规划甚至递归完成,但是如果是求几十亿甚至几百亿的时候,O(n)的时间复杂度显然不够看,并且也不允许我们开辟那么大的数组,此时就可以使用矩阵快速幂来求解这个递推式;

举个栗子:

对于斐波那契数列,f[1] = 1,f[2] = 1,f[n] = f[n-1]+f[n-2]

如果使用线性的递推,那么需要O(n)级别的时间复杂度,当n很大时,达到了几十亿的级别时，比较难以在规定时间内完成;

如果使用矩阵快速幂,那么我们需要构造两个矩阵A,B;

对于矩阵A,就是我们需要的结果矩阵,我们在其中放置两个初值,f[1],f[2],

对于矩阵B,我们会要求每次A,B相乘后,矩阵的大小和A相同,所以矩阵B是一个2*2矩阵;

且矩阵A和矩阵B相乘后,原f1要变为f2,f2要变为f3;

\[A=\begin{bmatrix} f1 & f2\\ \end{bmatrix}\]

\[B=\begin{bmatrix} 0 & 1\\ 1 & 1\\ \end{bmatrix}\]

则乘一次就能得到下一项，求第 项就求 ，乘的过程就能使用矩阵快速幂来加速了。