結果

問題 No.3036 Restricted Lucas (Easy)
ユーザー ats5515ats5515
提出日時 2018-04-02 00:39:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 111 ms / 2,000 ms
コード長 2,339 bytes
コンパイル時間 936 ms
コンパイル使用メモリ 88,812 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-08 13:11:38
合計ジャッジ時間 2,171 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD;

int zero;
int one;
int two;

int add(int a, int b)
{
	while (b != zero)
	{
		int c = (a & b) << one;
		a ^= b;
		b = c;
	}
	return a;
}
int sub(int a, int b)
{
	return add(a, add(~b, one));
}
int mul(int a, int b)
{
	int c = zero;
	while (b != zero)
	{
		if (b & one)
			c = add(c, a);
		b >>= one;
		a <<= one;
	}
	return c;
}
int msb(int a)
{
	int c = zero;
	while (a != zero)
	{
		a >>= one;
		c = add(c, one);
	}
	return c;
}
int mydiv(int a, int b)
{
	int q = zero;
	int c = sub(msb(a), msb(b));
	for (; c >= zero; c = sub(c, one))
	{
		int d = sub(a, b << c);
		if (d >= zero)
		{
			a = d;
			q |= one << c;
		}
	}
	return a;
}
void initmod() {
	int ten = mul(two, add(two, add(two, one)));
	MOD = one;
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = mul(MOD, ten);
	MOD = add(MOD, sub(ten, add(two, one)));

}
using Mat = vector<vector<int> >;
Mat matmul(Mat a, Mat b) {
	Mat res(two, vector<int>(two, zero));
	res[zero][zero] = add(mydiv(mul(a[zero][zero], b[zero][zero]), MOD), mydiv(mul(a[zero][one], b[one][zero]), MOD));
	res[one][zero] = add(mydiv(mul(a[one][zero], b[zero][zero]), MOD), mydiv(mul(a[one][one], b[one][zero]), MOD));
	res[zero][one] = add(mydiv(mul(a[zero][zero], b[zero][one]), MOD), mydiv(mul(a[zero][one], b[one][one]), MOD));
	res[one][one] = add(mydiv(mul(a[one][zero], b[zero][one]), MOD), mydiv(mul(a[one][one], b[one][one]), MOD));
	return res;
}
Mat matpow(Mat a, int b) {
	if (b == one)return a;
	if ((b & one) == zero) {
		return matpow(matmul(a, a), b >> one);
	}
	else {
		return matmul(matpow(matmul(a, a), b >> one), a);
	}
}
signed main() {
	int N;
	cin >> N;
	zero = N^N;
	one = abs(~zero);
	two = add(one, one);
	initmod();
	vector<int> A(N);
	Mat k(two, vector<int>(two));
	k[zero][zero] = one;
	k[zero][one] = one;
	k[one][zero] = one;
	k[one][one] = zero;
	for (int i = zero; i < N; i = add(i, one)) {
		cin >> A[i];
		Mat x = matpow(k, A[i]);
		cout << mydiv(add(x[one][zero], mul(x[one][one], two)), MOD) << endl;
	}

}
0