結果
問題 | No.2156 ぞい文字列 |
ユーザー |
|
提出日時 | 2022-12-10 20:37:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,922 bytes |
コンパイル時間 | 4,155 ms |
コンパイル使用メモリ | 256,292 KB |
最終ジャッジ日時 | 2025-02-09 09:17:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using namespace std; //#define DISABLE_PRINT #if defined(ENABLE_PRINT) && !defined(DISABLE_PRINT) #define P(...) fprintf(stderr, __VA_ARGS__) #define LP fprintf(stderr, "L: %d\n", __LINE__) #else #define P(...) ((void)0) #define LP ((void)0) #endif #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define ALL(x) x.begin(), x.end() using ll = long long; using ull = unsigned long long; const int INF = 1100100100; const ll INFLL = 1100100100100100100; using mint = atcoder::modint998244353; template <typename T, int Mod = 1> class Matrix { public: Matrix(int h, int w) : _h(h), _w(w) { _data = vector<vector<T>>(h, vector<T>(w)); } vector<T> &operator[](int i) { assert(i >= 0 && i < _h); return _data[i]; } Matrix operator+(const Matrix &r) const { Matrix v(*this); v += r; return v; } Matrix &operator+=(const Matrix &r) { rep(i, _h) rep(j, _w) { _data[i][j] += r._data[i][j]; _data[i][j] %= Mod; } return *this; } Matrix operator-(const Matrix &r) const { Matrix v(*this); v -= r; return v; } Matrix &operator-=(const Matrix &r) { rep(i, _h) rep(j, _w) { _data[i][j] -= r._data[i][j]; _data[i][j] += Mod; _data[i][j] %= Mod; } return *this; } Matrix operator*(const Matrix &r) { assert(_w == r._h); Matrix v(_h, r._w); rep(i, _h) rep(j, r._w) { v._data[i][j] = 0; rep(k, _w) { auto m = (_data[i][k] * r._data[k][j]) % Mod; v._data[i][j] += m; v._data[i][j] %= Mod; } } return v; } Matrix &operator*=(const Matrix &r) { assert(_w == _h && _w == r._w && r._w == r._h); auto v = (*this) * r; *this = v; return *this; } Matrix pow(ll x) { P("x: %lld\n", x); if (x == 1) { return *this; } auto tx = x / 2; auto tm = pow(tx); auto v = tm * tm; if (x % 2 == 1) { v = v * (*this); } return v; } void Dump() const { rep(i, _h) { rep(j, _w) { P("%5lld ", _data[i][j]); } P("\n"); } } private: int _h, _w; vector<vector<T>> _data; }; int main() { ll N; cin >> N; using MT = Matrix<ll, 998244353>; if (N == 2) { cout << 1 << endl; return 0; } MT m(2, 2); m[0][0] = 1; m[0][1] = 1; m[1][0] = 1; m[1][1] = 0; m.Dump(); m = m.pow(N - 2); m.Dump(); MT lm(2, 1); lm[0][0] = 2; lm[1][0] = 1; auto ans = m * lm; cout << (ans[0][0] + 998244352) % 998244353 << endl; return 0; }