백준 12987: Matrix Again

https://www.acmicpc.net/problem/12987

12987번: Matrix Again

 

풀이

분할 정복을 이용하여 쉽게 풀 수 있습니다.

 

$S_T=A+A^2+\dots+A^T$라고 하고, $S_T$를 빠르게 구해 봅시다.

$S_{T/2}=A+A^2+\dots+A^{T/2}$이기 때문에, $T$가 짝수일 땐 $S_T=S_{T/2}+A^{T/2}\times S_{T/2}$로 $S_T$를 구할 수 있고, $T$가 홀수일 땐 $S_T=S_{T/2}+A^{T/2}\times S_{T/2}+A^T$로 구할 수 있습니다.

$A^T$는 필요한 것들만 구해줍니다. 분할 정복 과정이 $S_T$를 구하는 것과 같기 때문에 문제에서 주어진 $A^K$를 구하는 과정에서 나오는 행렬들을 따로 저장해두었다가 $S_T$를 구할 때에 쓰면 됩니다.

 

코드

※살짝 가독성이 떨어질 수 있습니다.

시간복잡도는 $O(N^3\log K)$입니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q;
ll m, k, a[50][50], b[50][50][33], ans[50][50];
void multi(ll x, int p) {
    if(x==1) {
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) b[i][j][p]=a[i][j];
        return;
    }
    multi(x/2, ++p);
    ll w[50][50]={0};
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            for(int l=0; l<n; l++) w[i][j]+=b[i][l][p]*b[l][j][p]%m;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) w[i][j]%=m;
    if(x%2) for(int i=0; i<n; i++)
                for(int j=0; j<n; j++)
                    for(int l=0; l<n; l++) b[i][j][p-1]+=w[i][l]*a[l][j]%m;
    else for(int i=0; i<n; i++) for(int j=0; j<n; j++) b[i][j][p-1]=w[i][j];
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) b[i][j][p-1]%=m;
}
void solve(ll x, int p) {
    if(x==1) {
        for(int i=0; i<n; i++) for(int j=0; j<n; j++) ans[i][j]=a[i][j];
        return;
    }
    solve(x/2, ++p);
    ll ad[50][50]={0};
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            for(int l=0; l<n; l++) ad[i][j]+=b[i][l][p]*ans[l][j]%m;
    if(x%2) for(int i=0; i<n; i++)
                for(int j=0; j<n; j++) ad[i][j]+=b[i][j][p-1]%m;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) ans[i][j]+=ad[i][j]%m;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) ans[i][j]%=m;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k >> m;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) {
        cin >> a[i][j];
        a[i][j]=(a[i][j]%m+m)%m;
    }
    multi(k, 0);
    solve(k, 0);
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) cout << ans[i][j] << " ";
        cout << "\n";
    }
}