문제
행렬 제곱
풀이
알고리즘 자체는 행렬들을 분할정복으로 거듭제곱을 하는 식이 같지만, 구현이 행렬로 바뀜에 따라 어려움이 있어 다른 분의 코드를 가지고 왔다.
2중벡터로 행렬을 표현하고, 거듭제곱 부분에서 분할정복을 이용하는 코드이다.
거듭제곱을 하는 부분을 기억해두면 좋을 것 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
| matrix power(matrix a, ll r)
{
matrix res(n, vector<ll>(n));
for(int i = 0; i<n; i++)
res[i][i] = 1;
while(r>0){
if(r%2 == 1)
res = res * a;
r /= 2;
a = a * a;
}
return res;
}
|
소스 코드
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
| #include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;
ll n, b;
matrix operator*(const matrix &a, const matrix &b)
{
matrix res(n, vector<ll>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
res[i][j] += a[i][k] * b[k][j];
}
res[i][j] %= 1000;
}
}
return res;
}
// 행렬 a의 r제곱을 반환하는 함수
matrix power(matrix a, ll r)
{
matrix res(n, vector<ll>(n));
for(int i = 0; i<n; i++)
res[i][i] = 1;
while(r>0){
if(r%2 == 1)
res = res * a;
r /= 2;
a = a * a;
}
return res;
}
// 결과 행렬 출력
void printRes(const matrix &res)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << res[i][j] << " ";
}
cout << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> b;
matrix origin(n, vector<ll>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> origin[i][j];
}
}
printRes(power(origin, b));
return 0;
}
|
Reference
