結果

問題 No.1595 The Final Digit
コンテスト
ユーザー kobakoba_issa
提出日時 2021-07-09 22:38:03
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,753 bytes
コンパイル時間 4,333 ms
コンパイル使用メモリ 163,480 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 17:21:05
合計ジャッジ時間 3,607 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (1<<30)-1;
const ll LINF = (1LL<<60)-1;

#define rep(i, n) for (int i = 0; i < n; i++)
#define sz(a) (int)(a.size())

template<class T> 
bool chmax(T &a, T b) {if (a < b) {a = b;return true;}else return false;}

template<class T> 
bool chmin(T &a, T b) {if (a > b) {a = b;return true;}else return false;}

vector<vector<ll> > mod_prod_matrix(const vector<vector<ll> >& A, const vector<vector<ll> >& B, ll mod) {
    int l = A.size(), m = B.size(), n = B[0].size();
    vector<vector<ll> > res(l, vector<ll>(n, 0));
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < m; k++)
                res[i][j] = (res[i][j] + A[i][k]*B[k][j]%mod)%mod;
        }
    }
    return res;
}

vector<vector<ll> > mod_matrix_pow(const vector<vector<ll> >& A, ll n, ll mod) {
    int m = A.size();
    vector<vector<ll> > res(m, vector<ll>(m, 0));
    for (int i = 0; i < m; i++) res[i][i] = 1;
    if (n == 0)
        return res;
    else if (n % 2) {
        res = mod_matrix_pow(A, n-1, mod);
        return mod_prod_matrix(A, res, mod);
    }
    else {
        res = mod_matrix_pow(A, n/2, mod);
        return mod_prod_matrix(res, res, mod);
    }
}

//コーナーケースに気をつけろ！
int main() {
    vector<ll> p(3);  ll k;
    rep(i, 3)   cin >> p[i];
    cin >> k;
    vector<vector<ll> > B(3, vector<ll>(3, 0));
    rep(i, 3)   B[0][i] = 1;
    B[1][0] = 1;
    B[2][1] = 1;
    
    B = mod_matrix_pow(B, k-3, 10LL);
    int ans = 0;
    rep(i, 3)   ans = (ans + p[2-i] * B[0][i] % 10) % 10;
    cout << ans << endl;
    return 0;   
}

//小数点精度
//cout << fixed << std::setprecision(15) << y << endl;
0