[백준 12728번] n제곱 계산

문제 링크: https://www.acmicpc.net/problem/12728

12728번: n제곱 계산

 

<문제 풀이> 수학, 선형대수학, 행렬 거듭제곱

 

[구한 정수부분을 1000으로 나눈 나머지가 뒤에 세자리인데 음수도 나올 수 있으므로 C++로 구현할 때 음수 모듈러 처리를 해줘야됩니다.]

 

<C++ 소스코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test_case;
    cin >> test_case;
    for(int i=1; i<= test_case; i++){
        ll n;
        cin >> n;
        matrix a = { {6,-4}, {1, 0} };
        matrix res = power(a, n - 1);
        string ans = to_string((((28 * res[1][0] + 6 * res[1][1]) - 1) % 1000 + 1000) % 1000);
        ll size = ans.size();
        while (true) {
            if (size == 3) break;
            ans = "0" + ans;
            size++;
            
        }
        cout << "Case #" << i << ": " << ans << '\n';
     }
    
 
    return 0;
}