矩阵快速幂的写法（模板）

首先一般会定义一个结构体

struct matrix
{
	int a[n][m];
};

 

 

2*2的矩阵直接可以用两个for

matrix mul(matrix a, matrix b)
{
	matrix ret;
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			ret.a[i][j] = (a.a[i][0]*b.a[0][j]+a.a[i][1]*b.a[1][j]);
		}
	}
	return ret;
}

 

接下来就是O(n^3)的算法(如l*n的矩阵与n*m的矩阵相乘)

matrix mul(matrix a, matrix b)
{
	matrix ret;
	for(int i=0;i<l;i++)
	{
		for(int j=0;j<m;j++)
		{
			ret.a[i][j]=0;
			for(int k=0;k<n;k++)
			{
				ret.a[i][j] += a.a[i][k]*b.a[k][j];
			}
		}
	}
	return ret;
}

这个简单易懂，但是效率不太高，极易超时

以下是效率较高的

matrix mul(matrix a, matrix b)  
{  
	matrix ret;
    for(int i=0;i<l;i++)
	{
		for(int j=0;j<m;j++)
		{
			ret.a[i][j]=0;
		}
	} //初始化必不可少   
    for(int i=0;i<l;i++) 
	{
		for(int k=0;k<n;k++) 
		{
			 if(a.a[i][k])
			 {
			 	for(int j=0;j<m;j++)  
			 	{
			 		if(b.a[k][j]) 
					ret.a[i][j]+=a.a[i][k]*b.a[k][j];
			 	}
			 }		
		}    
	}  
	return ret;     
} 

 

综上，大致可以写成（以2*2的矩阵为例）

#include <iostream>
using namespace std;
struct matrix
{
	int a[2][2];
};
matrix mul(matrix a, matrix b)  
{  
	matrix ret; 
    for(int i=0;i<2;i++) 
	{
		for(int j=0;j<m;j++)  
		{
			ret.a[i][j] = a.a[i][0]*b.a[0][j]+a.a[i][1]*b.a[1][j];
		}	  
	}  
	return ret;     
}  
matrix mpower(matrix a, int n)
{
	matrix I;
	I.a[0][0] = I.a[1][1] = 1;
	I.a[0][1] = I.a[1][0] = 0;
	//将I初始化为单位矩阵
	while(n)
	{
		if(n&1) I = mul(I,a);
		a = mul(a,a);
		n>>=1;
	} 
	return I;
} 
int main()
{
	cin//先输入 
	//然后初始化矩阵 ，假设n个tmp矩阵相乘 
	tmp = mpower(tmp,n);
	//输出矩阵中的数
	return 0; 
}