#824169 (C++17) No.2156 ぞい文字列

• 問題: No.2156 ぞい文字列
• ユーザー: norikame
• 提出日時: 2022-12-09 22:21:51
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,600 bytes
• コンパイル時間: 4,556 ms
• コンパイル使用メモリ: 271,320 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-14 22:21:30
• 合計ジャッジ時間: 5,294 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	2 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	2 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	2 ms; 5,248 KB
testcase_12	AC	2 ms; 5,248 KB
testcase_13	AC	2 ms; 5,248 KB
testcase_14	AC	2 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	2 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	2 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB

ソースコード

// 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using ll = long long;

#define rep(i, n) for (int i=0; i<(int)(n); ++(i))
#define rep3(i, m, n) for (int i=(m); (i)<(int)(n); ++(i))
#define repr(i, n) for (int i=(int)(n)-1; (i)>=0; --(i))
#define rep3r(i, m, n) for (int i=(int)(n)-1; (i)>=(int)(m); --(i))
#define all(x) (x).begin(), (x).end()

const ll mod = 998244353LL;
using mint = modint998244353;
template<typename T>
struct Matrix {
	int h, w;
	vector<vector<T>> d;
	Matrix() {}
	Matrix(int h, int w, T val=0) : h(h), w(w), d(h, vector<T>(w, val)) {}
	Matrix& unit() {
		assert(h == w);
		rep(i, h) d[i][i] = 1;
		return *this;
	}
	const vector<T>& operator[](int i) const { return d[i]; }
	vector<T>& operator[](int i) { return d[i]; }
	Matrix operator*(const Matrix& a) const {
		assert(w == a.h);
		Matrix r(h, a.w);
		rep(i, h) rep(k, w) rep(j, a.w) {
			r[i][j] += d[i][k] * a[k][j];
		}
		return r;
	}
	Matrix pow(long long t) const {
		assert(h == w);
		if (!t) return Matrix(h, h).unit();
		if (t == 1) return *this;
		Matrix r = pow(t>>1);
		r = r * r;
		if (t&1) r = r * (*this);
		return r;
	}
};

int main() {
	ll n;
	cin >> n;
	int nl = 0;
	ll tn = 1;
	while (tn < n) {
		tn *= 2;
		++nl;
	}
	Matrix<mint> mat(5, 5);
	mat.d = { 
		{ 1, 0, 1, 0, 0 },
		{ 0, 1, 0, 0, 0 },
		{ 1, 1, 0, 0, 0 },
		{ 0, 0, 0, 1, 1 },
		{ 0, 0, 0, 1, 0 }
	};
	mat = mat.pow(n-1);
	vector<mint> a = { 0, 1, 0, 0, 1 }, rval(5);
	rep(i, 5) rep(j, 5) rval[i] += mat.d[i][j] * a[j];
	mint res = rval[0] + rval[2];
	cout << res.val() << endl;
	return 0;
}