#936493 (C++23) No.2600 Avator Height

• 問題: No.2600 Avator Height
• ユーザー: 👑 amentorimaru
• 提出日時: 2023-12-05 01:59:29
• 言語: C++23 (gcc 12.3.0 + boost 1.83.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	595 ms; 5,248 KB
testcase_02	AC	600 ms; 5,376 KB
testcase_03	AC	590 ms; 5,376 KB
testcase_04	AC	592 ms; 5,376 KB
testcase_05	AC	601 ms; 5,376 KB
testcase_06	AC	621 ms; 5,376 KB
testcase_07	AC	606 ms; 5,376 KB
testcase_08	AC	600 ms; 5,376 KB
testcase_09	AC	591 ms; 5,376 KB
testcase_10	AC	603 ms; 5,376 KB
testcase_11	AC	596 ms; 5,376 KB
testcase_12	AC	600 ms; 5,376 KB
testcase_13	AC	606 ms; 5,376 KB
testcase_14	AC	613 ms; 5,376 KB
testcase_15	AC	597 ms; 5,376 KB
testcase_16	AC	600 ms; 5,376 KB
testcase_17	AC	608 ms; 5,376 KB
testcase_18	AC	606 ms; 5,376 KB
testcase_19	AC	623 ms; 5,376 KB
testcase_20	AC	608 ms; 5,376 KB
testcase_21	AC	615 ms; 5,376 KB
testcase_22	AC	612 ms; 5,376 KB
testcase_23	AC	602 ms; 5,376 KB
testcase_24	AC	276 ms; 5,376 KB
testcase_25	AC	623 ms; 5,376 KB

ソースコード

#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";
	}
}