結果

問題 No.8036 Restricted Lucas (Easy)
コンテスト
ユーザー kurenai3110
提出日時 2018-04-02 01:12:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 1,819 bytes
コンパイル時間 1,741 ms
コンパイル使用メモリ 66,016 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:26:06
合計ジャッジ時間 1,544 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;

const int zero = false;
const int one = true;
const int two = one + true;
const int three = two + true;
const int four = three + true;
const int five = four + true;
const int six = five + true;
const int seven = six + true;
const int eight = seven + true;
const int nine = eight + true;
const int ten = nine + true;

ll product(ll a, ll b) {
	if (b == zero)return zero;
	ll cnt = one;
	ll ret = a;
	while (b >= cnt + cnt) {
		ret += ret;
		cnt += cnt;
	}

	return ret + product(a, b - cnt);
}

const int MOD = product(product(product(product(product(product(product(product(ten, ten), ten), ten), ten), ten), ten), ten), ten) + seven;

ll mod(ll a, ll b) {
	while (a >= b) {
		ll m = b;
		while (a >= m + m)m += m;
		a -= m;
	}
	return a;
}

vector<vector<ll>> mul(vector<vector<ll>>&a, vector<vector<ll>>&b, ll p) {
	vector<vector<ll>>c(a.size(), vector<ll>(b.size()));
	
	for (ll i = zero; i<a.size(); i++) {
		for (ll k = zero; k<b.size(); k++) {
			for (ll j = zero; j<b[zero].size(); j++) {
				c[i][j] = mod((c[i][j] + product(a[i][k],b[k][j])), p);
			}
		}
	}
	return c;
}

vector<vector<ll>> pow(vector<vector<ll>>&a, ll n, ll p) {
	vector<vector<ll>>b(a.size(), vector<ll>(a.size()));
	for (ll i = zero; i<a.size(); i++) {
		b[i][i] = one;
	}
	while (n>zero) {
		if (n & one) b = mul(a, b, p);
		a = mul(a, a, p);
		n >>= one;
	}
	return b;
}

ll fibonacci(ll n, ll p) {
	vector<vector<ll>>a(two, vector<ll>(two));
	a[zero][zero] = one; a[zero][one] = one;
	a[one][zero] = one; a[one][one] = zero;
	a = pow(a, n + one, p);
	return a[one][zero];
}

int main() {
	int T; cin >> T;

	for (int i = zero; i < T; i++) {
		int N; cin >> N;
		
		cout << mod(fibonacci(N-two, MOD) + fibonacci(N, MOD), MOD) << endl;
	}

	return zero;
}
0