結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
👑 |
提出日時 | 2025-08-22 23:13:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 122 ms / 2,000 ms |
コード長 | 3,256 bytes |
コンパイル時間 | 2,122 ms |
コンパイル使用メモリ | 205,040 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-22 23:14:11 |
合計ジャッジ時間 | 2,886 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
/* [Original Python code — included per AtCoder rule] MOD = 998244353 def power(A, e): result = [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))] while e: if e % 2: result = multiply(result, A) A = multiply(A, A) e //= 2 return result def multiply(A, B): return [[sum(x * y % MOD for x, y in zip(A_row, B_col)) % MOD for B_col in zip(*B)] for A_row in A] def multiply_vector(M, v): return [sum(M[i][j] * v[j] % MOD for j in range(len(v))) % MOD for i in range(len(M))] X = [ [1, 1, 1, 1, 0, 0, 0], # 1 [1, 1, 1, 1, 0, 0, 0], # -1 ok [0, 0, 1, 1, 1, 1, 0], # 2 [0, 0, 1, 1, 1, 1, 0], # -2 [1, 0, 0, 0, 1, 1, 1], # 4 [1, 0, 0, 0, 1, 1, 1], # -4 [1, 0, 0, 0, 0, 0, 1], # -1 ng ] Y = [ [1, 1], [1, 1], ] def solve(): N = int(input()) ans = multiply_vector(power(X, N), [1, 0, 0, 0, 0, 0, 0])[0] ans -= multiply_vector(power(Y, N), [1, 0])[0] print(ans % MOD) if __name__ == "__main__": T = int(input()) for _ in range(T): solve() */ #include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 998244353; using Mat = vector<vector<ll>>; static Mat identity(int n) { Mat I(n, vector<ll>(n, 0)); for (int i = 0; i < n; ++i) I[i][i] = 1; return I; } static Mat multiply(const Mat& A, const Mat& B) { int n = (int)A.size(); int m = (int)A[0].size(); // also B.size() int p = (int)B[0].size(); Mat C(n, vector<ll>(p, 0)); for (int i = 0; i < n; ++i) { for (int k = 0; k < m; ++k) { ll aik = A[i][k] % MOD; if (aik == 0) continue; for (int j = 0; j < p; ++j) { C[i][j] = (C[i][j] + aik * (B[k][j] % MOD)) % MOD; } } } return C; } static vector<ll> multiply_vector(const Mat& M, const vector<ll>& v) { int n = (int)M.size(); int m = (int)v.size(); vector<ll> res(n, 0); for (int i = 0; i < n; ++i) { ll s = 0; for (int j = 0; j < m; ++j) { s = (s + (M[i][j] % MOD) * (v[j] % MOD)) % MOD; } res[i] = s; } return res; } static Mat power(Mat A, long long e) { int n = (int)A.size(); Mat R = identity(n); while (e) { if (e & 1) R = multiply(R, A); A = multiply(A, A); e >>= 1; } return R; } // Constants from the original code const Mat X = { {1, 1, 1, 1, 0, 0, 0}, // 1 {1, 1, 1, 1, 0, 0, 0}, // -1 ok {0, 0, 1, 1, 1, 1, 0}, // 2 {0, 0, 1, 1, 1, 1, 0}, // -2 {1, 0, 0, 0, 1, 1, 1}, // 4 {1, 0, 0, 0, 1, 1, 1}, // -4 {1, 0, 0, 0, 0, 0, 1}, // -1 ng }; const Mat Y = { {1, 1}, {1, 1}, }; void solve() { long long N; cin >> N; vector<ll> vX = {1, 0, 0, 0, 0, 0, 0}; vector<ll> vY = {1, 0}; ll a = multiply_vector(power(X, N), vX)[0]; ll b = multiply_vector(power(Y, N), vY)[0]; ll ans = (a - b) % MOD; if (ans < 0) ans += MOD; // Python's `%` yields non-negative; emulate it cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; if (!(cin >> T)) return 0; while (T--) solve(); return 0; }