結果

問題 No.1595 The Final Digit
コンテスト
ユーザー aogera
提出日時 2025-12-28 15:19:46
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 681 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,315 ms
コンパイル使用メモリ 349,664 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-28 15:19:53
合計ジャッジ時間 5,692 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/extc++.h>
using namespace std;
using ll=long long;
using mat=vector<vector<ll>>;
int main(){
	ll p,q,r,K;
	cin>>p>>q>>r>>K;
	const ll MOD=10;
	mat A={{1,1,1},{1,0,0},{0,1,0}};
	auto multi=[&](mat X,mat Y){
		mat res(3,vector<ll>(3));
		for(int i=0;i<3;i++) for(int j=0;j<3;j++){
			for(int k=0;k<3;k++){
				res[i][j]+=X[i][k]*Y[k][j]%MOD;
				res[i][j]%=MOD;
			}
		}
		return res;
	};
	const int B=62;
	vector<mat> dbl(B);
	dbl[0]=A;
	for(int b=1;b<B;b++){
		dbl[b]=multi(dbl[b-1],dbl[b-1]);
	}
	mat now=A;
	K-=4;
	for(int b=B-1;b>=0;b--){
		if(K>=(1LL<<b)){
			K-=(1LL<<b);
			now=multi(now,dbl[b]);
		}
	}
	cout<<(now[0][0]*r+now[0][1]*q+now[0][2]*p)%10<<endl;

}
0