• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

矩阵快速幂的原理和构造技巧

开发技术 开发技术 2周前 (04-07) 6次浏览

矩阵和快速幂是两个大家都耳熟能详的概念,我们在学习矩阵快速幂这一概念之前,先稍微复习一下这两个概念。

矩阵乘法

矩阵快速幂的原理和构造技巧
这是矩阵乘法的定义,不难发现,它的大小由前面的行数和后面的列数共同决定,也就是说,矩阵乘法并不符合乘法交换律。这也限制了,如果我们要对一个矩阵反复相乘,这个矩阵应该是一个方阵。至于这点的应用会在下文提到,大家只需要先熟悉一下矩阵乘法的规则。

快速幂

快速幂算法应该也是一个很经典的算法。它的的核心思想就是每一步都把指数分成两半,而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小,所需要执行的循环次数也变小,而最后表示的结果却一直不会变。
单独说这两个知识其实没什么关系,但是有时候我们需要对一个矩阵进行多次相乘,也就是求幂。这时候我们可以把快速幂和矩阵乘法相结合,快速的求出一个矩阵的幂次。
至于这种算法的应用,这里先暂时按下不表,先用代码把这个算法简单实现一下。
为了方便,我们这里直接把矩阵封装成类,所有运算在类里定义。

struct Matrix{
	static const int N=15;
	ll a[N][N];
	Matrix(ll e=0){
		for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)a[i][j]=e*(i==j);
	}
	Matrix mul(Matrix A,Matrix B){
		Matrix ans(0);
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				for (int k=1;k<=n;k++){
					ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%mod;
				}
			}
		}
		return ans;
	}
	Matrix ksm(Matrix A,ll b){
		Matrix ans(1);
		while (b){
			if (b&1)ans=mul(ans,A);
			A=mul(A,A);b>>=1;
		}
		return ans;
	}
}tmp;

这个算法的复杂度级别是O(n3logn)
接下来给大家介绍这个算法除了求解完全的板子题以外,还有什么其他作用。

递推式的求解。

提到递推式,斐波那契数列是绕不开的一环。所以我们先从斐波那契数列出发,介绍矩阵快速幂的一种用法。
斐波那契数列的递推规律,F(n)=F(n-1)+F(n-2);
我们要构造转移矩阵B,不难发现。我们只要让转移矩阵乘递推后项可以成为递推前项就可以了。这样我们就可以把问题转化为转移矩阵的幂次和常数相乘的问题
矩阵快速幂的原理和构造技巧
矩阵快速幂的原理和构造技巧
也就是这张图说的求出转移矩阵的n-1次方然后F(n)实际上就等于转移矩阵的n-1次方的第一行乘初始矩阵的第一列。F(0)=0;所以答案就是转移矩阵的n-1次方的第一行第一列。
下面放一个模板题的代码
poj3070;

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int t,n=2,k;
const int MOD = 10000;
struct Matrix{
	static const int N=15;
	ll a[N][N];
	Matrix(ll e=0){
		for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)a[i][j]=e*(i==j);
	}
	Matrix mul(Matrix A,Matrix B){
		Matrix ans(0);
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				for (int k=1;k<=n;k++)
					ans.a[i][j]=(ans.a[i][j]+A.a[i][k]*B.a[k][j])%MOD;
		return ans;
	}
	Matrix ksm(Matrix A,ll b){
		Matrix ans(1);
		while (b){
			if (b&1)ans=mul(ans,A);
			A=mul(A,A);b>>=1;
		}
		return ans;
	}
}tmp;
int main()
{
    int q;
    while (scanf("%d", &q) && q != -1)
    {
        tmp.a[1][1]=1,tmp.a[1][2]=1,tmp.a[2][1]=1,tmp.a[2][2]=0;
        if(q==0)printf("0n");
        else {
            tmp=tmp.ksm(tmp,q-1);
            printf("%lldn", tmp.a[1][1]);
        }
    }
    return 0;
}

解决了这个问题我们只需要处理的就是如何构造这个矩阵的问题。这里先给大家一张图片矩阵快速幂的原理和构造技巧
前几种会比较好理解,第三种和第四种,实际上就是利用二项式定理,构造(n+1-1)²这类东西来构造矩阵。只要把前后关系找对,构造难度不大。
给大家几个例子方便理解。
带常数的矩阵快速幂的原理和构造技巧
带平方的矩阵快速幂的原理和构造技巧
需要一起构造前缀和的
矩阵快速幂的原理和构造技巧


程序员灯塔
转载请注明原文链接:矩阵快速幂的原理和构造技巧
喜欢 (0)