結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
![]() |
提出日時 | 2025-07-07 14:15:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 4,721 bytes |
コンパイル時間 | 4,499 ms |
コンパイル使用メモリ | 257,760 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-07-10 22:22:49 |
合計ジャッジ時間 | 4,510 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
#include <bits/stdc++.h> using namespace std; using std::cerr; using std::cin; using std::cout; #if __has_include(<atcoder/all>) #include <atcoder/all> using mint = atcoder::modint998244353; istream &operator>>(istream &is, mint &a) { int t; is >> t; a = t; return is; } ostream &operator<<(ostream &os, mint a) { return os << a.val(); } #endif typedef long double ld; #define long long long #define uint unsigned int #define ull unsigned long #define overload3(a, b, c, name, ...) name #define rep3(i, a, b) for (int i = (a); i < (b); i++) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(i, n) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define per2(i, n) per3(i, 0, n) #define per1(n) per2(i, n) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define all(a) a.begin(), a.end() #define UNIQUE(a) \ sort(all(a)); \ a.erase(unique(all(a)), a.end()) #define sz(a) (int)a.size() #define vec vector #ifndef DEBUG #define cerr \ if (0) \ cerr // #undef assert // #define assert(...) void(0) #undef endl #define endl '\n' #endif template <typename T> ostream &operator<<(ostream &os, vector<T> a) { const int n = a.size(); rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template <typename T, size_t n> ostream &operator<<(ostream &os, array<T, n> a) { rep(i, n) { os << a[i]; if (i + 1 != n) os << " "; } return os; } template <typename T> istream &operator>>(istream &is, vector<T> &a) { for (T &i : a) is >> i; return is; } template <typename T, typename S> bool chmin(T &x, S y) { if ((T)y < x) { x = (T)y; return true; } return false; } template <typename T, typename S> bool chmax(T &x, S y) { if (x < (T)y) { x = (T)y; return true; } return false; } template <typename T> void operator++(vector<T> &a) { for (T &i : a) ++i; } template <typename T> void operator--(vector<T> &a) { for (T &i : a) --i; } template <typename T> void operator++(vector<T> &a, int) { for (T &i : a) i++; } template <typename T> void operator--(vector<T> &a, int) { for (T &i : a) i--; } template <typename T> struct M { vector<vector<T>> a; int n, m; M(int n, int m) : n(n), m(m), a(n, vector<T>(m)) {} M(int n = 0) : M<T>(n, n) {} vector<T> &operator[](int k) { return a[k]; } const vector<T> &operator[](int k) const { return a[k]; } static M I(int n) { M mat(n); rep(i, n) mat[i][i] = 1; return mat; } M &operator+=(const M &b) { rep(i, n) rep(j, m)(*this)[i][j] += b[i][j]; return *this; } M &operator-=(const M &b) { rep(i, n) rep(j, m)(*this)[i][j] -= b[i][j]; return *this; } M &operator*=(const M &b) { int l = b.m; vector c(n, vector<T>(l)); rep(i, n) rep(j, m) rep(k, l) c[i][k] += (*this)[i][j] * b[j][k]; a.swap(c); return *this; } M &operator^=(long k) { M b = M::I(n); while (k) { if (k & 1) b *= *this; *this *= *this; k >>= 1; } a.swap(b.a); return *this; } M operator+(const M &b) const { return (M(*this) += b); } M operator-(const M &b) const { return (M(*this) -= b); } M operator*(const M &b) const { return (M(*this) *= b); } M operator^(const M &b) const { return (M(*this) ^= b); } }; template <typename T> pair<int, T> GaussElimination(M<T> &a, bool LE = false) { int n = a.n, m = a.m; int rank = 0, je = LE ? m - 1 : m; mint det = 1; rep(j, je) { int idx = -1; rep(i, rank, n) { if (a[i][j].x) { idx = i; break; } } if (idx == -1) { det = 0; continue; } if (rank != idx) { det = -det; swap(a[rank], a[idx]); } det *= a[rank][j]; if (LE && a[rank][j].x != 1) { mint coeff = a[rank][j].inv(); rep(k, j, m) a[rank][k] *= coeff; } int is = LE ? 0 : rank + 1; rep(i, is, n) { if (i == rank) continue; if (a[i][j].x) { mint coeff = a[i][j] / a[rank][j]; rep(k, j, m) a[i][k] -= a[rank][k] * coeff; } } rank++; } return make_pair(rank, det); } void solve() { M<mint> a(7); rep(i, 6) { a[i][i] = 1; a[i ^ 1][i] = 1; if (i < 4) { a[i + 2][i] = 1; a[(i + 2) ^ 1][i] = 1; } } a[6][4] = a[6][5] = 1; a[0][4] = a[0][5] = 1; a[6][6] = a[0][6] = 1; long n; cin >> n; a ^= n; cout << a[0][0] - mint(2).pow(n - 1) << endl; } int main() { // srand((unsigned)time(NULL)); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int t = 1; cin >> t; while (t--) solve(); }