矩阵快速幂 斐波那契数列

矩阵快速幂 斐波那契数列

首先是矩阵乘法 

在矩阵乘法中满足以下运算律：

1.(AB)C=a(BC) 2.(A+B)C=AC+BC 3.C(A+B)=CA+CB

在普通的乘法中，一个数乘1还是等于它本身，在矩阵乘法中也有这么一个“1”，它就是单位矩阵

不同于普通乘法中的单位1，对于不同矩阵他们的单位矩阵大小是不同的

对于n∗mn*mn∗m的矩阵，它的单位矩阵大小为m∗mm*mm∗m，对于m∗nm*nm∗n的矩阵，它的单位矩阵大小为n∗nn*nn∗n

也就是说单位矩阵都是正方形的，这是因为只有正方形的矩阵能保证结果和前一个矩阵形状相同

单位矩阵的元素非0即1，从左上角到右下角的对角线上元素皆为1，其他皆为0

矩阵快速幂就是把快速幂和矩阵乘法结合在一起

#include
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48 ; ch=getchar();}
	return x*f;
}
long long m = 1e9+7;
long long n;
struct Matrix{
	long long mat[10][10]; //定义一个结构体
}a;
void init(Matrix &res){
	memset(res.mat,0,sizeof(res.mat));
	for(register int i(1) ; i<=2 ; i=-~i) res.mat[i][i] = 1;  //单位矩阵
}
Matrix mul(Matrix a,Matrix b){
	Matrix res;
	memset(res.mat,0,sizeof(res.mat));
	for(register int i(1) ; i<=2 ; i=-~i){
		for(register int k(1) ; k<=2 ; k=-~k){ //注意，先循环K比先循环J快
			for(register int j(1) ; j<=2 ; j=-~j){
				res.mat[i][j] += (a.mat[i][k]%m) * (b.mat[k][j]%m); //矩阵乘法
				res.mat[i][j] = res.mat[i][j]%m;
			}
		}
	}
	return res;
}
Matrix qp(Matrix a,long long n){
	Matrix res,base = a;
	init(res);
	while(n){
		if(n%2 == 1) res = mul(res,base); //快速幂，和普通的原理一样
		base = mul(base,base);
		n/=2;
	}
	return res;
}
int main(){
	cin >> n;
	a.mat[1][1] = 1;
	a.mat[1][2] = 1;
	a.mat[2][1] = 1;
	a.mat[2][2] = 0; //推出的矩阵
	a = qp(a,n-2); 
	cout << (a.mat[1][1]%m+a.mat[1][2]%m)%m;
	return 0;
}