結果

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

ソースコード

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