[PS] 백준 10830번: 행렬 제곱

행렬 제곱

천억제곱을 하는데 어떻게 숫자를 유지해야하는지 감이 안잡혔었는데,
어차피 찾는건 마지막 세자리 숫자니 계속 모듈러 1000 연산을 하면 되는 문제였다.
알고리즘 분류를 읽어보니 분할 정복을 써야 하는 문제인 듯 했지만 미리 곱해두고 나중에 찾아서 곱하는 방식으로 풀었는데 AC 되었다.

메모리 제한이 256MB라 도대체 메모리 초과가 날 이유가 없는데, 자꾸 메모리 초과가 떠서 디버깅하는데에 한참 걸렸다.
문제는 반복문에서 i를 long long으로 안해둬서 i가 음수가 되어,

for(long long i = 1; i < B; i *= 2) {
    vvi.push_back(move(mult(vvi.back(), vvi.back())));
}

이 부분에서 무한대로 push_back 하고 있었더라... i가 음수이면 암만 i에 2를 곱해도 B보다 커질리가 없으니...

 

#include <bits/stdc++.h>

#define FOR(i, n) for(int i = 0; i < int(n); i++)
#define FORL(e, s) for(auto &e : s)
#define endl "\n"
#define vi vector<int>

using namespace std;

int N;
long long B;

vi mult(vi &v1, vi &v2) {
    vi res(N * N, 0);
    FOR(i, N)
        FOR(j, N)
            FOR(k, N)
                res[i * N + j] += v1[i * N + k] * v2[k * N + j];

    FORL(e, res) e = e % 1000;
    return res;    
}

int main() {
    cin >> N >> B;
    vi V;
    FOR(i, N) FOR(j, N) {
        int input; cin >> input;
        V.push_back(input);
    }

    vector<vi> vvi; vvi.push_back(V);
    for(long long i = 1; i < B; i *= 2) {
        vvi.push_back(move(mult(vvi.back(), vvi.back())));
    }

    FOR(i, N) FOR(j, N) V[i * N + j] = 0;
    FOR(i, N) FOR(j, N) if(i == j) V[i * N + j] = 1;

    long long limit = B;
    while (limit > 0) {
        long long idx = 0;
        while(true) {
            if(pow(2, idx + 1) > limit) {
                V = move(mult(V, vvi[idx]));
                limit -= pow(2, idx);
                break;
            }
        idx += 1;
        }
    }

    FOR(i, N) {
        FOR(j, N)
            cout << V[i * N + j] << " ";    
        cout << endl;
    }
    return 0;
}