蓝桥杯算法提高VIP-矩阵乘方 （C++代码）

解题思路:

快速幂运算和矩阵乘法结合即可

注意事项:

任何矩阵的0次方等于单位矩阵

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
const int MAX=2;
typedef struct 
{
	int m[MAX][MAX];
}Matrix;

Matrix I=
{
	1,0,
	0,1,
};
Matrix ZERO=
{
	0,0,
	0,0,
};
Matrix matrixmul(Matrix a,Matrix b,int m)//矩阵乘法
{
	Matrix c;
	for(int i=0;i<MAX;i++)
	{
		for(int j=0;j<MAX;j++)
		{
			c.m[i][j]=0;
			for(int k=0;k<MAX;k++)
			{
				c.m[i][j]+=(a.m[i][k]*b.m[k][j])%m;
			}
			c.m[i][j]%=m;
		}	
	} 
	return c;
} 
Matrix quickpow(Matrix p,long long n,int m)
{
	Matrix ans = I;
	while(n>0)
	{
		if(n&1) ans = matrixmul(ans,p,m);
		n=n>>1;
		p=matrixmul(p,p,m);
	}
	return ans;
}
void print(Matrix p)
{
	cout<<p.m[0][0]<<" "<<p.m[0][1]<<endl;
	cout<<p.m[1][0]<<" "<<p.m[1][1]<<endl; 
}
int main(void)
{
	int b,m;
	Matrix p;
	cin>>b>>m;
	if(b!=0)
	{
		cin>>p.m[0][0]>>p.m[0][1]>>p.m[1][0]>>p.m[1][1];
		p = quickpow(p,b,m);
		print(p); 
	}
	else if(b==0 && m!=1) 
	{
		print(I);
	}
	else 
	{
		print(ZERO);
	}
	return 0;
}