結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー IL_mstaIL_msta
提出日時 2018-04-02 19:06:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 2,502 bytes
コンパイル時間 1,033 ms
コンパイル使用メモリ 86,496 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-08 13:31:19
合計ジャッジ時間 1,730 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 3 ms
4,380 KB
testcase_02 AC 20 ms
4,376 KB
testcase_03 AC 21 ms
4,380 KB
testcase_04 AC 20 ms
4,380 KB
testcase_05 AC 20 ms
4,380 KB
testcase_06 AC 20 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using
namespace
std;

typedef
long
long
LL;

LL
zero=false;
LL
one=true;
LL
MOD;
LL
getMod();

LL
kake(LL
A,LL
B){
LL
ret=zero;
vector<LL>
keta;
while(B){
	if(B&one){
		keta.push_back(one);
	}else{
		keta.push_back(zero);
	}
	B>>=one;
}
reverse(keta.begin(),keta.end());
int
size=keta.size();
for(int
i=zero;i<size;++i){
	ret<<=one;
	if(keta[i]){
		ret+=A;
	}
}
return
ret;
}
vector<LL>
V;
LL
ama(LL
A){
	int
	size=V.size();
	for(int
	i=zero;i<size;++i){
		while(A>=V[i]){
			A-=V[i];
		}
	}
return
A;
}
vector<vector<LL>>
MUL(vector<vector<LL>>&
A,vector<vector<LL>>&
B){
	LL
	mod=MOD;
	int
	R=A.size();
	int
	cen=A[zero].size();
	int
	C=B[zero].size();
	vector<vector<LL>>
	ans(R,vector<LL>(C,zero));
	for(int
	row=zero;row<R;++row){
		for(int
		col=zero;col<C;++col){
	for(int
	inner=zero;inner<cen;++inner){
ans[row][col]=(ans[row][col]+kake(A[row][inner],B[inner][col]));
	ans[row][col]=ama(ans[row][col]);
			}
		}
	}
	return
	ans;
}


vector<vector<LL>>
powMod(const
vector<vector<LL>>&
mat,LL
N,LL
mod=MOD){
	int
	R=mat.size();
	int
	C=mat[zero].size();
	
	vector<vector<LL>>
	I(R,vector<LL>(C,zero));
	for(int
	i=zero;i<R&&i<C;++i){
		I[i][i]=one;
	}
	if(N==zero){
		return
		I;
	}
	vector<vector<LL>>mul(R,vector<LL>(C)),ans(R,vector<LL>(C));
	ans=I;
	mul=mat;
	while(N){
		if(N&one){
			ans=MUL(ans,mul);
		}
		N>>=one;
		mul=MUL(mul,mul);
	}
	return
	ans;
}
int
main(){
	MOD=getMod();
{
	LL
	temp=MOD;
	while(temp>=zero){
		V.push_back(temp);
		temp<<=one;
	}
	reverse(V.begin(),V.end());
}
	int
	T;
	cin>>T;
	vector<vector<LL>>R(one<<one,vector<LL>(one<<one,one));
	R[one][one]=zero;
	vector<vector<LL>>A(one<<one,vector<LL>(one));
	A[zero][zero]=one;
	A[one][zero]=one<<one;
	while(T--){
		LL
		N;
		cin>>N;
		if(N==one){
			cout<<one<<endl;
			continue;
		}
		vector<vector<LL>>res=powMod(R,N-one);
		vector<vector<LL>>ans=MUL(res,A);
		cout<<ans[zero][zero]<<endl;
	}
	return zero;
}

LL
getMod(){
	long
	long
	MOD=zero;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;

MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;

MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;

MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;

MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;

MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
	return MOD;
}
0