結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
![]() |
提出日時 | 2025-08-22 23:09:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 937 ms / 2,000 ms |
コード長 | 2,052 bytes |
コンパイル時間 | 1,402 ms |
コンパイル使用メモリ | 110,072 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-22 23:11:16 |
合計ジャッジ時間 | 4,416 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; std::vector<std::vector<long long>> mul(const std::vector<std::vector<long long>> &v1, const std::vector<std::vector<long long>> &v2, long long mod = 998244353) { std::vector<std::vector<long long>> ans; if (v1.size() != v2[0].size()) return ans; ans.assign(v1.size(), std::vector<long long> (v2[0].size(), 0)); for (int i = 0; i < v1.size(); ++i) for (int j = 0; j < v2[0].size(); ++j) for (int k = 0; k < v2.size(); ++k) ans[i][j] = (ans[i][j] + v1[i][k] * v2[k][j]) % mod; return ans; } std::vector<std::vector<long long>> pow(std::vector<std::vector<long long>> v, long long k, long long mod = 998244353) { std::vector<std::vector<long long>> ans; if (v.size() != v[0].size()) return ans; ans.assign(v.size(), std::vector<long long> (v.size(), 0)); for (int i = 0; i < v.size(); ++i) ans[i][i] = 1; for (; k > 0; k >>= 1, v = mul(v, v, mod)) if (k & 1) ans = mul(v, ans, mod); return ans; } int main() { const int mod = 998244353; int t; cin >> t; const int siz = 9; vector<vector<long long>> bs(siz, vector<long long> (siz)); int val[siz] = {1, -1, 2, -2, 4, -4, 8, -8, 0}; int c[4] = {1, -1, 2, -2}; for (int i = 0; i < siz; ++i) { if (val[i] == 8) { ++bs[siz - 3][i]; ++bs[siz - 1][i]; ++bs[2][i]; ++bs[3][i]; } else if (val[i] == 0) { ++bs[siz - 1][i]; ++bs[siz - 3][i]; ++bs[2][i]; ++bs[3][i]; } else { for (int j = 0; j < 4; ++j) { int tmp = val[i] * c[j]; if (abs(tmp) > 8) { if (val[i] == 8) tmp = c[j]; else continue; } for (int k = 0; k < siz; ++k) { if (val[k] == tmp) { ++bs[k][i]; } } } } } while (t--) { long long n; cin >> n; auto mat = bs; auto res = pow(mat, n, mod); long long ans = (res[siz - 3][0]) % mod; cout << ans << endl; } }