結果
問題 |
No.1595 The Final Digit
|
ユーザー |
![]() |
提出日時 | 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 | } | ^
ソースコード
#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; }