結果

問題 No.1595 The Final Digit
ユーザー sawfish
提出日時 2022-10-23 22:59:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,145 bytes
コンパイル時間 554 ms
コンパイル使用メモリ 64,768 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-02 11:41:11
合計ジャッジ時間 1,280 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

using namespace std;
using LL = long long;
using ULL = unsigned long long;

constexpr int MOD = 10;

struct M {
    LL p[3][3] = {
            {1, 1, 1},
            {1, 0, 0},
            {0, 1, 0},
    };

    M mul(M b, LL m) {
        M c;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                c.p[i][j] = 0;
                for (int k = 0; k < 3; k++) {
                    c.p[i][j] += (this->p[i][k] * b.p[k][j]) % m;
                }
            }
        }
        return c;
    }
};

struct E : M {
    LL p[3][3] = {
            {1, 0, 0},
            {0, 1, 0},
            {0, 0, 1},
    };
};

M pow(M, LL, LL);

int main() {
    LL p, q, r, K;
    cin >> p >> q >> r >> K;

    M A, B = pow(A, K - 3, MOD);

    LL ans = 0;
    ans = (ans + B.p[0][0] * r) % MOD;
    ans = (ans + B.p[0][1] * q) % MOD;
    ans = (ans + B.p[0][2] * p) % MOD;

    cout << ans << endl;
}

M pow(M a, LL b, LL m) {
    if (b == 0) return E();
    if (b == 1) return M();
    M ret = pow(a, b / 2, m);
    ret = ret.mul(ret, m);
    if (b % 2 == 1) ret = ret.mul(a, m);
    return ret;
}
0