結果

問題 No.3037 Restricted Lucas (Hard)
ユーザー satanicsatanic
提出日時 2018-04-02 02:01:30
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,837 bytes
コンパイル時間 1,097 ms
コンパイル使用メモリ 87,356 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-08 13:15:32
合計ジャッジ時間 1,779 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <functional>
#define int long long

int z;
int o = !z;
int two = o << o;
int seven = std::minus<int>()(two << two, o);

int MOD;

std::vector<std::vector<int>> a, b;

int suc(int& x) {
	return x = std::plus<int>()(x, o);
}

std::vector<std::vector<int>> mul(std::vector<std::vector<int>> x, std::vector<std::vector<int>> y) {
	std::vector<std::vector<int>> r(x.size(), std::vector<int>(y[z].size(), z));
	for (int i = z; i < x.size(); suc(i)) {
		for (int j = z; j < y[z].size(); suc(j)) {
			for (int k = z; k < x[z].size(); suc(k)) {
				r[i][j] = std::modulus<int>()(std::plus<int>()(r[i][j], std::multiplies<int>()(x[i][k], y[k][j])), MOD);
			}
		}
	}
	return r;
}

void pow_(int p) {
	while (p) {
		if (p & o) a = mul(a, b);
		b = mul(b, b);
		p >>= o;
	}
}

int solve(int n) {
	if (n == o) return o;

	a = std::vector<std::vector<int>>(two, std::vector<int>(two, o));
	a[o][o] = z;
	b = a;

	pow_(std::minus<int>()(n, two));
	return std::modulus<int>()(std::plus<int>()(a[z][z], (a[z][o] << o)), MOD);
}

void init_mod() {
	std::string s;
	s = std::plus<std::string>()(s, std::to_string(o));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(z));
	s = std::plus<std::string>()(s, std::to_string(seven));
	MOD = std::stoi(s);
}

signed main() {
	init_mod();

	int t;
	std::cin >> t;
	for (int _ = z; _ < t; suc(_)) {
		int n;
		std::cin >> n;
		std::cout << solve(n) << std::endl;
	}

	return z;
}
0