Power of Matrix UVA - 11149

原题链接
考察:矩阵快速幂
两种方法,但我都没想到()
思路一:

??显然(1,1)+(1,2)-(2,2)就是答案.

Code

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 40,M =80,Mod = 10;
int A[N][N],a[M][M],b[M][M],n,k;
void mul(int a[][M],int b[][M])
{
	int res[M][M] = {0};
	for(int i=0;i<2*n;i++)
	  for(int j=0;j<2*n;j++)
	    for(int k=0;k<2*n;k++)
	      res[i][j] = (res[i][j]+(LL)a[i][k]*b[k][j])%Mod;
	memcpy(a,res,sizeof res);
}
void solve()
{
	for(int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
	    printf("%d%c",(a[i][j]+a[i][j+n]-a[i+n][j+n])%Mod,j==n-1?‘\n‘:‘ ‘);
}
int main()
{
	int kcase = 0;
    while(scanf("%d%d",&n,&k)!=EOF&&(n+k))
	{
		memset(a,0,sizeof a);
		if(kcase) printf("\n");
		kcase++;
		for(int i=0;i<n;i++)
		  for(int j=0;j<n;j++)
		  {
		  	scanf("%d",&A[i][j]);
		  	a[i][j] = A[i][j];
		  	if(i==j) a[i][j+n] = 1,a[i+n][j+n] = 1;
		  }
		if(k==1)
		{
			for(int i=0;i<n;i++)
			  for(int j=0;j<n;j++)
			    printf("%d%c",A[i][j]%Mod,j==n-1?‘\n‘:‘ ‘);
			continue;
		} 
		memcpy(b,a,sizeof a); 
		k--;
		while(k)
		{
			if(k&1) mul(a,b);
			mul(b,b);
			k>>=1;
		}
		solve();
	}
	return 0; 
}

??思路二就是利用递归和分治了,具体看抽风大佬的题解吧,我懒得写了,这种写法适用于结构体,数组比较麻烦,主要是结构体进行运算实际就是声明了一个新的结构体接收,然后以前的值不改变(.

Go

Power of Matrix UVA - 11149

原文：https://www.cnblogs.com/newblg/p/14863943.html