結果

問題 No.2600 Avator Height
コンテスト
ユーザー amentorimaru
提出日時 2023-12-05 01:59:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 623 ms / 2,000 ms
コード長 809 bytes
コンパイル時間 3,896 ms
コンパイル使用メモリ 181,352 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-26 23:58:38
合計ジャッジ時間 20,562 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using mint = modint998244353;

vector<mint> mul(vector<mint>& a, vector<mint>& b) {
	vector<mint> res = { a[0] * b[0] + a[1] * b[2],a[0] * b[1] + a[1] * b[3],a[2] * b[0] + a[3] * b[2],a[2] * b[1] + a[3] * b[3] };
	return res;
}

vector<mint> power(long long n, vector<mint>& mut) {
	vector<mint> res = { 1,0,0,1 };
	if (n == 0)
		return res;
	auto pow = mul(mut, mut);
	res = power(n / 2, pow);
	if (n % 2)res = mul(res, mut);
	return res;
}

int main() {
	int q;
	cin >> q;
	vector<mint> mut = { 0,1,1,1 };
	for(int i=0; i<q; i++){
		int n;
		cin>>n;
		auto res = power(n - 1, mut);
		cout << (5 * (res[0] + res[1]) * (res[0] + res[1]) - (res[0] + 3 * res[1]) * (res[0] + 3 * res[1])).val() << "\n";
	}
}
0