結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
![]() |
提出日時 | 2025-08-25 12:06:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 3,037 bytes |
コンパイル時間 | 587 ms |
コンパイル使用メモリ | 46,136 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-25 12:06:20 |
合計ジャッジ時間 | 1,559 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:116:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 116 | scanf("%d", &tn); | ~~~~~^~~~~~~~~~~ main.cpp:120:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 120 | scanf("%lld", &n); | ~~~~~^~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3243.cc: No.3243 Multiplication 8 1 - yukicoder */ #include<cstdio> #include<algorithm> using namespace std; /* constant */ const int M = 7; const int MOD = 998244353; /* typedef */ using ll = long long; template<const int MOD> struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; } MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; } explicit operator int() const { return v; } MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator-() const { return MI(MOD - v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } bool operator==(const MI m) const { return v == m.v; } bool operator!=(const MI m) const { return v != m.v; } MI pow(long long n) const { // a^n % MOD MI pm = 1, a = *this; while (n > 0) { if (n & 1) pm *= a; a *= a; n >>= 1; } return pm; } MI inv() const { return pow(MOD - 2); } MI operator/(const MI m) const { return *this * m.inv(); } MI &operator/=(const MI m) { return (*this = *this / m); } }; using mi = MI<MOD>; using vec = mi[M]; using mat = vec[M]; /* global variables */ /* subroutines */ inline void initvec(const int n, vec a) { fill(a, a + n, 0); } inline void initmat(const int n, mat a) { for (int i = 0; i < n; i++) initvec(n, a[i]); } inline void unitmat(const int n, mat a) { initmat(n, a); for (int i = 0; i < n; i++) a[i][i] = 1; } inline void copymat(const int n, const mat a, mat b) { for (int i = 0; i < n; i++) copy(a[i], a[i] + n, b[i]); } inline void mulmat(const int n, const mat a, const mat b, mat c) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { c[i][j] = 0; for (int k = 0; k < n; k++) c[i][j] += a[i][k] * b[k][j]; } } inline void powmat(const int n, const mat a, ll b, mat c) { mat s, t; copymat(n, a, s); unitmat(n, c); while (b > 0) { if (b & 1) { mulmat(n, c, s, t); copymat(n, t, c); } mulmat(n, s, s, t); copymat(n, t, s); b >>= 1; } } inline void mulmatvec(const int n, const mat a, const vec b, vec c) { for (int i = 0; i < n; i++) { c[i] = 0; for (int j = 0; j < n; j++) c[i] += a[i][j] * b[j]; } } /* main */ int main() { int tn; scanf("%d", &tn); while (tn--) { ll n; scanf("%lld", &n); // 1, -1, 2, -2, 4, -4, -8 mat ma = { { 1, 1, 0, 0, 1, 1, 1 }, // 1 { 1, 1, 0, 0, 0, 0, 0 }, // -1 { 1, 1, 1, 1, 0, 0, 0 }, // 2 { 1, 1, 1, 1, 0, 0, 0 }, // -2 { 0, 0, 1, 1, 1, 1, 0 }, // 4 { 0, 0, 1, 1, 1, 1, 0 }, // -4 { 0, 0, 0, 0, 1, 1, 1 }, // -8 }; mat mb; powmat(M, ma, n, mb); mi s = mb[0][0] - mi(2).pow(n - 1); printf("%d\n", (int)s); } return 0; }