結果

問題 No.2156 ぞい文字列
コンテスト
ユーザー norikame
提出日時 2022-12-09 22:21:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,600 bytes
コンパイル時間 3,789 ms
コンパイル使用メモリ 261,016 KB
最終ジャッジ日時 2025-02-09 08:23:05
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 

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