結果

問題 No.8037 Restricted Lucas (Hard)
コンテスト
ユーザー kurenai3110
提出日時 2018-04-02 01:21:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 2,191 bytes
コンパイル時間 641 ms
コンパイル使用メモリ 65,996 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:26:30
合計ジャッジ時間 1,326 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;

ll add(ll a, ll b)
{
	while (b != zero)
	{
		ll c = (a & b) << one;
		a ^= b;
		b = c;
	}
	return a;
}
ll sub(ll a, ll b)
{
	while (b != zero)
	{
		ll c = (~a & b) << one;
		a ^= b;
		b = c;
	}
	return a;
}

const int two = add(one, true);
const int three = add(two, true);
const int four = add(three, true);
const int five = add(four, true);
const int six = add(five, true);
const int seven = add(six, true);
const int eight = add(seven, true);
const int nine = add(eight, true);
const int ten = add(nine, true);


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

	return add(ret, product(a, sub(b, cnt)));
}

const int MOD = add(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 >= add(m, m))m = add(m, m);
		a = sub(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=add(i ,one)) {
		for (ll k = zero; k<b.size(); k=add(k, one)) {
			for (ll j = zero; j<b[zero].size(); j = add(j, one)) {
				c[i][j] = mod((add(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 = add(i, one)) {
		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, add(n, one), p);
	return a[one][zero];
}

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

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

	return zero;
}
0