이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 13 번째 글 입니다.
목차
실버1 : 분할 정복 문제이다.
생각
특정 행렬을 10번 곱하라는 의미는, 곧 이렇게 해석 된다.
\[\begin{align} A^10 & = A^2 \times A^5 \\ &= A^2 \times A^2 \times A^3 \\ &= A^2 \times A^2 \times A^2 \times A \\ \end{align}\]결국, 10이라는 숫자가 들어왔을 때, 2로 나누어지면 A를 제곱하고 ans에 업데이트, 나누어지지 않으면 A를 한번 곱하고, A제곱을 곱하여 업데이트 한다.
typedef vector<vector<int>> matrix;
matrix operator * (const matrix &a, const matrix &b) {
int n = int(a.size());
matrix ans(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
ans[i][j] += a[i][k] * b[k][j];
}
ans[i][j] %= 1000;
}
}
return ans;
}
matrix go(matrix a, long long b){
int n = int(a.size());
matrix ans(n, vector<int>(n));
if (b == 0) return ans;
if (b % 2) ans = ans * a;
return ans * go(a*a, b/2);
}
int main(){
int n;
long long b;
cin >> n >> b;
matrix a(n, vector<int>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
matrix ans == calc(a, b);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << ans[i][j] << ' ';
}cout << '\n';
}
}