結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー kmjpkmjp
提出日時 2018-04-01 22:37:13
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,415 bytes
コンパイル時間 1,444 ms
コンパイル使用メモリ 161,152 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-26 05:58:18
合計ジャッジ時間 1,925 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=(x-x);x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
//-------------------------------------------------------

string S="baaaaaaaah";
ll mo;
ll N;
ll T;

ll fib(ll k,ll a,ll b) {
	int z=k-k;
	a=k==k;
	b=a+a+a;
	int c=a+a;
	if(k==a) return a;
	if(k==a+a) return b;
	k-=a+a;
	
	ll R['c'-'a']['c'-'a']={{a,z},{z,a}};
	ll A['c'-'a']['c'-'a']={{a,a},{a,z}};
	
	while(k) {
		if(k%c) {
			ll S['c'-'a']['c'-'a'];
			S[z][z]=(A[z][z]*R[z][z]+A[z][a]*R[a][z])%mo;
			S[z][a]=(A[z][z]*R[z][a]+A[z][a]*R[a][a])%mo;
			S[a][z]=(A[a][z]*R[z][z]+A[a][a]*R[a][z])%mo;
			S[a][a]=(A[a][z]*R[z][a]+A[a][a]*R[a][a])%mo;
			swap(S,R);
		}
		ll T['c'-'a']['c'-'a'];
		T[z][z]=(A[z][z]*A[z][z]+A[z][a]*A[a][z])%mo;
		T[z][a]=(A[z][z]*A[z][a]+A[z][a]*A[a][a])%mo;
		T[a][z]=(A[a][z]*A[z][z]+A[a][a]*A[a][z])%mo;
		T[a][a]=(A[a][z]*A[z][a]+A[a][a]*A[a][a])%mo;
		swap(T,A);
		k>>=a;
	}
	
	return (b*R[z][z]+R[z][a])%mo;
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FORR(c,S) {
		c-='/';
		c-=x==x;
		c-=x==x;
	}
	mo=atoi(S.c_str());
	
	cin>>T;
	while(T--) {
		cin>>N;
		cout<<fib(N,N,N)<<endl;
	}
	
}


int main(int argc,char** argv){
	solve();
	return argc-argc;
}
0