快速幂-矩阵快速幂-线性dp优化

快速幂

当求某一正整数 $a$ 的 $n$ 次幂 $a^n$ 时，常用的做法是将 $a$ 连续乘以 $n$ 次，其时间复杂度为 $O(n)$ 。 事实上，该问题有时间复杂度为 $O(logn)$ 的解法。其核心思想是：$$a^n=\{\begin{array}{ll}{a}^{n/2}\ast a^{n/2},& \text{n 为偶数}\\ a^{n/2}\ast a^{n/2}\ast a,& \text{in 为奇数}\end{array}$$

代码如下：

	/**
	 * 求 a 的 n 次幂
	 * @param a
	 * @param n
	 * @return
	 */
	long pow(int a, int n) {
			long res = 1;
			
			while(n != 0) {
				if(n % 2 == 1) {
					res *= a; 
				}
				n /= 2;
				a *= a;
			}
			
			return res;
		}

矩阵快速幂

将上述的整数乘法改成矩阵乘法，就可快速幂推广至矩阵快速幂。

代码如下：

	/**
	 * 矩阵 a 的 n 次幂
	 * @param a 
	 * @param n 
	 * @return
	 */
	int[][] pow(int[][] a, int n) {
		int k = a.length;
		int[][] res = new int[k][k];
		for(int i = 0; i < k; i++) {
			res[i][i] = 1;
		}
		
		while(n != 0) {
			if(n % 2 == 1) {
				res = mul(res, a);
			}
			n /= 2;
			a = mul(a, a);
		}
		
		return res;
	}

	/**
	  * 矩阵乘法
	 * @param a
	 * @param b
	 * @return
	 */
	int[][] mul(int[][] a, int[][] b) {
		int a_row = a.length;
		int b_col = b[0].length;
		int n = a[0].length; //a的列数等于b的行数
		int[][] res = new int[a_row][b_col];
		
		for(int i = 0; i < a_row; i++) {
			for(int j = 0; j < b_col; j++) {
				for(int k = 0; k < n; k++) {
					res[i][j] += a[i][k] * b[k][j];
				}
			}
		}
		
		return res;
	}

线性dp优化

一组 $DP$ 状态，其实等价于一个向量。而DP状态的转移方程，可以是对一个向量做变形的矩阵。那么本质上从一个向量到另一个状态的向量，是可以通过一个矩阵来做到。矩阵具有结合律，我们可以先对右半部分矩阵用快速幂得到一个终极的变形矩阵，再乘以向量，就可以把 $O(n)$ 的计算优化到 $O(log(n))$。 （转自简书——DP的五类优化-快速幂，四边形不等式）

例题：

1、$Fibonacci$ 数列

递推式：$F_n=F_{n-1}+F_{n-2},(n>2)$
$dp$ 状态转移方程：$dp[n]=dp[n-1]+dp[n-2],(n>2)$

由 $Fibonacci$ 数列的递推式可以得到如下矩阵关系式：
$$\left(\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{F}_{n-1}\\ F_{n-2}\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^{n-2}\left(\begin{array}{c}{F}_2\\ F_1\end{array}\right)$$
故该问题转换成矩阵的 $n$ 次幂，实现代码如下：

	/**
	 * 求f(n)
	 * @param n
	 * @return
	 */
	int fibonacci(int n) {
		if(n == 0) {
			return 0;
		}
		if(n <= 2) {
			return 1;
		}
		
		int[][] initial = {{1}, {1}}; //f(2), f(1)
		int[][] transition = {{1, 1}, {1, 0}}; //转换矩阵
		int[][] result = new int[2][2]; //结果矩阵 f(n), f(n-1)
		result = mul(pow(transition, n - 2), initial);
		
		return result[0][0];
	}

注：$mul$ 函数和 $pow$ 函数均为矩阵快速幂部分中的对应函数

现在有一个问题——如何得到转换矩阵？

未想到通解。。。

2、CCF202006第四题 $1246(digits)$

后续更新。。。

最后

以上就是慈祥高跟鞋为你收集整理的快速幂-矩阵快速幂-线性dp优化的全部内容，希望文章能够帮你解决快速幂-矩阵快速幂-线性dp优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。