結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー toriaezuACtoriaezuAC
提出日時 2018-04-02 17:32:33
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,494 bytes
コンパイル時間 655 ms
コンパイル使用メモリ 56,368 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-26 06:41:11
合計ジャッジ時間 1,340 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <iostream>
using namespace std;
using ull = unsigned long long;

ull Adder(ull a, ull b, ull carry) {
	ull ret = 0;
	for (ull mask = 1; mask != 0; mask <<= 1) {
		ull am = (a & mask);
		ull bm = (b & mask);
		ull rm = am ^ bm ^ carry;
		ret |= rm;
		carry = (am & bm | am & carry | bm & carry) << 1;
	}
	return ret;
}

ull Plus(ull a, ull b) {
	return Adder(a, b, 0);
}

ull Minus(ull a, ull b) {
	return Adder(a, ~b, 1);
}

ull Mul(ull a, ull b) {
	ull ret = 0;
	for (ull mask = 1; mask != 0; mask <<= 1, a <<= 1) {
		ull bm = (b & mask);
		if (bm) {
			ret = Plus(ret, a);
		}
	}
	return ret;
}

ull Mod(ull dividend) {
	const ull Modulo = 1000000007;
	for (ull divisor = Modulo << 34; divisor >= Modulo; divisor >>= 1) {
		if (dividend >= divisor) {
			dividend = Minus(dividend, divisor);
		}
	}
	return dividend;
}

struct Hoge {
	ull k;
	ull l;
};

Hoge FormHoge(ull i) {
	if (i == 0) return Hoge{ 1, 0 };
	if (i == 1) return Hoge{ 0, 1 };
	ull half = i >> 1;
	if ((half << 1) != i) {
		Hoge sub = FormHoge(Minus(i, 1));
		return Hoge{ sub.l, Mod(Plus(sub.k, sub.l)) };
	}

	Hoge tmp = FormHoge(half);
	ull new_k = Mod(Plus(Mul(tmp.k, tmp.k), Mul(tmp.l, tmp.l)));
	ull new_l = Mod(Mul(tmp.l, Plus(tmp.k << 1, tmp.l)));
	return Hoge{ new_k, new_l };
}

ull Lucas(ull i) {
	Hoge hoge = FormHoge(i);
	return Mod(Plus(hoge.k << 1, hoge.l));
}

int main() {
	ull T;
	cin >> T;
	for (ull i = 0; i < T; i = Plus(i, 1)) {
		ull a;
		cin >> a;
		cout << Lucas(a) << endl;
	}
	return 0;
}
0