Leetcode-Solutions-1/Matrix exponentiatiion.cpp at master · rs1820/Leetcode-Solutions-1 · GitHub

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
#define N 101
int ar[N][N],I[N][N];
void mul(int A[][N], int B[][N], int dim)
{
	int res[dim+1][dim+1];
	for(int i=1;i<=dim;i++)
	{
		for(int j=1;j<=dim;j++)
		{
			res[i][j]=0;
			for(int k=1;k<=dim;k++)
			{
				res[i][j] += A[i][k]*B[k][j];
			}
		}
	}
	for(int i=1;i<=dim;i++)
	{
		for(int j=1;j<=dim;j++)
		{
			A[i][j] = res[i][j];
		}
	}
}
void power(int A[][N], int dim, int n)
{
	for(int i=1;i<=dim;i++)
	{
		for(int j=1;j<=dim;j++)
		{
			if(i==j)
			{
				I[i][j]=1;
			}
			else
			{
				I[i][j]=0;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		mul(I,A,dim);
	}
	for(int i=1;i<=dim;i++)
	{
		for(int j=1;j<=dim;j++)
		{
			A[i][j] = I[i][j];
		}
	}
}
void printMat(int A[][N], int dim)
{
	for(int i=1;i<=dim;i++)
	{
		for(int j=1;j<=dim;j++)
		{
			cout<<A[i][j]<<" ";
		}
		cout<<endl;
	}
}
int main()
{
	int t,dim,n;
	cin>>t;
	while(t--)
	{
		cin>>dim>>n;
		for(int i=1;i<=dim;i++)
		{
			for(int j=1;j<=dim;j++)
			{
				cin>>ar[i][j];
			}
		}
		power(ar,dim,n);
		printMat(ar,dim);
	}
}