矩阵快速幂 笔记加理解

1.何为快速幂

补充一个公式证明：

1.1学习快速幂的好文章

http://t.csdn.cn/agKop

1.2快速幂取模代码（对1000取模）

ll fastPower(ll base,ll power){
	ll result=1;
	while(power>0){
		if(power&1) result=result*base%1000;
		power>>=1;
		base=(base*base)%1000;
	}
	return result;
}
1
2
3
4
5
6
7
8
9

2.矩阵快速幂

2.1详细讲解

顾名思义，就是快速地求矩阵的幂。B站上Schtonn UP主的视频特别好，我就是看他的才看懂的。视频名称：看图学会矩阵快速幂（求斐波那契数列）

现在我简单讲一下。

斐波那契数列：

根据第二个式子，我们可以定义一个矩阵来表示f(x)的状态。如图：

那么，f(x+1)的状态就应该是：

那么，如何由f(x)状态转为f(x+1)状态呢？
引入另一个矩阵M，我们需要找到这个矩阵M的具体值，使得

根据矩阵乘法的规则可知，M矩阵应是两行两列（M有两列才可以分别和f(x-1),f(x-2)相乘,又因为右边式子有两行，所以说明M有两行)

那么设：

则有：

得：

由

得 a=1,b=1,c=1,d=0,即：

把M矩阵乘以我们定义的矩阵，就相当于把当前矩阵转移到了下一个状态。比如M乘以f(x)状态的矩阵，就得到f(x+1)状态的矩阵。

那么我们把矩阵M乘以n次，再乘以f(x)，是不是就得到f(x+n)状态的矩阵？也就得到了f(x+n)的值。

设这里f(x)的状态表示x=3时f(3)的状态。
那么

就表示f(x+2)也就是f(5)时的状态。我算出来是等于3f(x-1)+2f(x-2),而f(x-1)=f(2)=1,f(x-2)=f(1)=1。
所以f(5)=3f(x-1)+2f(x-2)=5。
斐波拉契为：1 1 2 3 5
也可验证上述结论正确。

现在，我们可以得出结论：

就是往后推算K位。
此时我们再定义一个初始矩阵

也就是

所以

得出的矩阵里的数相加就是斐波那契数列的第k+2位的值。

2.2 代码

#include
using namespace std;
typedef long long ll;
struct node{
	ll mat[2][2];
}x,y;//用结构体存数组方便代替函数返回二维数组

int main(){
	ll fastPower(ll power);
	ll n;
	cin>>n;	
	if(n==1||n==2) cout<<1;
	cout<<fastPower(n);
}

ll fastPower(ll power){
	if(power==1||power==2) return 1;
	if(power==3) return 2;
	power-=3;
	node mult(node x,node y);
	node result;
	node base;
	
	result.mat[0][0]=1;
	result.mat[0][1]=0;
	result.mat[1][0]=0;
	result.mat[1][1]=1;
	
	base.mat[0][0]=1;
	base.mat[0][1]=1;
	base.mat[1][0]=1;
	base.mat[1][1]=0;
	
	while(power>0){
		if(power&1) result=mult(base,result);
		power>>=1;
		base=mult(base,base);
	}
	
	return result.mat[0][0]+result.mat[0][1]+result.mat[1][0]+result.mat[1][1];
}

node mult(node x,node y){
	node t;
	t.mat[0][0]=x.mat[0][0]*y.mat[0][0]+x.mat[0][1]*y.mat[1][0];
	t.mat[0][1]=x.mat[0][0]*y.mat[0][1]+x.mat[0][1]*y.mat[1][1];
	t.mat[1][0]=x.mat[1][0]*y.mat[0][0]+x.mat[1][1]*y.mat[1][0];
	t.mat[1][1]=x.mat[1][0]*y.mat[0][1]+x.mat[1][1]*y.mat[1][1];
	return t;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50