結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
|
提出日時 | 2025-08-24 01:35:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 2,242 bytes |
コンパイル時間 | 4,190 ms |
コンパイル使用メモリ | 257,968 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-24 01:35:45 |
合計ジャッジ時間 | 5,222 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template <class T> bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template <class T> bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; namespace cho { using namespace std; template <typename T> struct matrix { int h, w; std::vector<std::vector<T>> d; matrix() { } matrix(int _h, int _w, T val = 0) : h(_h), w(_w), d(_h, vector<T>(_w, val)) { } matrix(vector<vector<T>> const& dat) : h(dat.size()), w(0), d(dat) { if (h > 0) w = d[0].size(); } static matrix unit(int n) { matrix uni(n, n, 0); for (int i = 0; i < n; i++) uni[i][i] = 1; return uni; } const vector<T>& operator[](int i) const { return d[i]; } vector<T>& operator[](int i) { return d[i]; } matrix& operator*=(const matrix& a) { return *this = (*this) * a; } matrix operator*(const matrix& a) const { assert(w == a.h); matrix r(h, a.w); for (int i = 0; i < h; i++) for (int k = 0; k < w; k++) for (int j = 0; j < a.w; j++) { r[i][j] += d[i][k] * a[k][j]; } return r; } matrix pow(long long t) const { assert(h == w); matrix res = matrix::unit(h); matrix x = (*this); while (t > 0) { if (t & 1) res = res * x; x = x * x; t >>= 1; } return res; } }; } // namespace cho using mint = atcoder::modint998244353; cho::matrix<mint> one7(7, 7); void solve() { ll n; cin >> n; mint ans = 0; ans += one7.pow(n)[0][0]; ans -= mint(2).pow(n - 1); cout << ans.val() << "\n"; cout << flush; } int main() { rep(i, 0, 2) { rep(j, 0, 2) { one7[i * 2 + j][i * 2 + j] = 1; one7[i * 2 + j][i * 2 + 1 - j] = 1; one7[i * 2 + j][(i + 1) * 2 + j] = 1; one7[i * 2 + j][(i + 1) * 2 + 1 - j] = 1; } } { one7[4][4] = 1; one7[4][5] = 1; one7[4][0] = 1; one7[4][6] = 1; } { one7[5][4] = 1; one7[5][5] = 1; one7[5][0] = 1; one7[5][6] = 1; } { one7[6][6] = 1; one7[6][0] = 1; } int t = 1; cin >> t; while (t--) solve(); }