BOJ - 행렬 곱셈(10830)

실버1 : 분할 정복 문제이다.

생각

특정 행렬을 10번 곱하라는 의미는, 곧 이렇게 해석 된다.

$$\begin{array}{rl}{A}^{1}0& =A^2\times A^5\\ & =A^2\times A^2\times A^3\\ & =A^2\times A^2\times A^2\times A\end{array}$$

결국, 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';
    }
}

Reference

• 백준(10830번) - 행렬 곱셈