結果
問題 | No.1595 The Final Digit |
ユーザー |
![]() |
提出日時 | 2021-07-10 01:07:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 939 bytes |
コンパイル時間 | 2,562 ms |
コンパイル使用メモリ | 200,972 KB |
最終ジャッジ日時 | 2025-01-22 23:25:27 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/modint> using namespace std; //using namespace atcoder; //using mint = modint1000000007; typedef long long ll; #define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I) vector< vector<ll> > E = {{1,0,0},{0,1,0},{0,0,1}}; vector< vector<ll> > A = {{1,1,1},{1,0,0},{0,1,0}}; vector<vector<ll>> calc(vector<vector<ll>> X,ll a){ if(a == 0) return E; auto R = calc(X,a/2); vector<vector<ll>> res = {{0,0,0},{0,0,0},{0,0,0}}; vector<vector<ll>> res1 = {{0,0,0},{0,0,0},{0,0,0}}; FOR(i,0,3){ FOR(j,0,3){ FOR(k,0,3){ ( res[i][j] += R[i][k]*R[k][j] ) %= 10; } } } if(a & 1)FOR(i,0,3){ FOR(j,0,3){ FOR(k,0,3){ ( res1[i][j] += X[i][k]*res[k][j] ) %= 10; } } } if(a&1){ return res1; }else{ return res; } } int main(){ ll K,p,q,r; cin >> p >> q >> r >> K; auto X = calc(A,K-3); ll ans = X[0][0]*r%10 + X[0][1]*q%10 + X[0][2]*p%10; cout << ans % 10 << endl; }