結果

問題 No.8036 Restricted Lucas (Easy)
コンテスト
ユーザー ciel
提出日時 2018-03-09 23:55:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 1,733 bytes
コンパイル時間 648 ms
コンパイル使用メモリ 71,408 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-10 21:05:07
合計ジャッジ時間 1,383 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

long long mul(long long a,long long b){
	long long ret=false;
	for(;b;b>>=true){
		if(b&true)ret+=a;
		a+=a;
	}
	return ret;
}

long long _div(long long a,long long b){
	long long ret=false;
	for(;a>=b;){
		int i=false;
		for(;a>=b<<i;i++);
		i--;
		a-=b<<i;
		ret|=(long long)true<<i;
	}
	return ret;
}
long long mod(long long a,long long b){
	return a-mul(_div(a,b),b);
}

typedef vector<long long>V;
const long long mo=true|true<<-~false|true<<-~-~false|true<<-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false;
V M(const V &x,const V &y){
	int a=false,b=true,c=b+b,d=b+b+b,e=b+b+b+b;
	V z(e);
	z[a]=mod(mul(x[a],y[a])+mul(x[b],y[c]),mo);
	z[b]=mod(mul(x[a],y[b])+mul(x[b],y[d]),mo);
	z[c]=mod(mul(x[c],y[a])+mul(x[d],y[c]),mo);
	z[d]=mod(mul(x[c],y[b])+mul(x[d],y[d]),mo);
	return z;
}

int main(){
	int T;
	for(cin>>T;T--;){
		long long N;
		cin>>N;N--;
		V e={true,false,false,true};
		V x={true,true,true,false};
		for(;N;N>>=true){
			if(N&true)e=M(e,x);
			x=M(x,x);
		}
		cout<<mod(e[false]+(e[true]<<true),mo)<<endl;
	}
}
0