結果

問題 No.1595 The Final Digit
ユーザー riano
提出日時 2021-07-09 21:50:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,503 bytes
コンパイル時間 1,829 ms
コンパイル使用メモリ 173,784 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 15:55:31
合計ジャッジ時間 2,594 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::vector<std::vector<long long int> > pw_matrix(std::vector<std::vector<long long int> >&, long long int)':
main.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
   42 | }
      | ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define Pr pair<ll,ll>
#define Tp tuple<ll,ll,ll>
using Graph = vector<vector<int>>;

ll mod = 10;


//行列累乗 matrix power
//modをglobalに定義しておく
vector<vector<ll>> pw_matrix(vector<vector<ll>> &M,ll n){
    if(n==1) return M;
    if(n%2==1){
        auto K = pw_matrix(M,n-1);
        int a = M.size();
        vector<vector<ll>> L(a,vector<ll>(a));
        rep(i,a){
            rep(j,a){
                ll b = 0;
                rep(k,a) b += (M[i][k]*K[k][j])%mod;
                L[i][j] = b%mod;
            }
        }
        return L;
    }
    if(n%2==0){
        auto K = pw_matrix(M,n/2);
        int a = M.size();
        vector<vector<ll>> L(a,vector<ll>(a));
        rep(i,a){
            rep(j,a){
                ll b = 0;
                rep(k,a) b += (K[i][k]*K[k][j])%mod;
                L[i][j] = b%mod;
            }
        }
        return L;
    }
}

    

int main() {
    ll a[3];
    rep(i,3) cin >> a[i];
    swap(a[0],a[2]);
    ll K; cin >> K;
    //rep(i,3) cout << a[i] << endl;
    //main関数内 sizeは適宜買える
    vector<vector<ll>> M(3,vector<ll>(3,0)); //もとの行列
    //行列の成分を代入
    rep(i,3) M[0][i] = 1;
    M[1][0] = 1; M[2][1] = 1;
    auto S = pw_matrix(M,K-3);
    ll ans = 0;
    rep(i,3){ //size変える
        ans += (S[0][i]*a[i])%mod;
        ans %= mod;
    }
    cout << ans << endl;
}
0