結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
![]() |
提出日時 | 2025-08-22 22:03:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,189 ms / 2,000 ms |
コード長 | 2,145 bytes |
コンパイル時間 | 349 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 79,156 KB |
最終ジャッジ日時 | 2025-08-22 22:03:18 |
合計ジャッジ時間 | 4,630 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
mod = 998244353 def mat_mul(A, B, f = 1): #行列同士と行列ベクトルの積を計算 n = len(A) if f: #modの計算を行うか分岐 global mod if isinstance(B[0], list): #行列同士の積か分岐 C = [[0 for _ in range(n)] for _ in range(n)] for y in range(n): for x in range(n): for d in range(n): C[y][x] += A[y][d] * B[d][x] % mod C[y][x] %= mod return C else: C = [0 for _ in range(n)] for y in range(n): for x in range(n): C[y] += A[y][x] * B[x] % mod C[y] %= mod return C else: if isinstance(B[0], list): C = [[0 for _ in range(n)] for _ in range(n)] for y in range(n): for x in range(n): for d in range(n): C[y][x] += A[y][d] * B[d][x] return C else: C = [0 for _ in range(n)] for y in range(n): for x in range(n): C[y] += A[y][x] * B[x] return C def pow_mat(M, B, n): #行列の累乗(M = 正規行列、 B = 遷移行列) while n: if n & 1: M = mat_mul(B, M) B = mat_mul(B, B) n >>= 1 return M def main(): n = int(input()) I = {1: 0, -1: 1, 2: 2, -2: 3, 4: 4, -4: 5, -8: 6} A = [1, -1, 2, -2, 4, -4, -8] B = [1, -1, 2, -2] M = [[0] * 9 for _ in range(9)] for y in range(7): a = A[y] for b in B: if a == -8 and abs(b) == 2: continue c = a * b if c == 8: idx = 7 else: idx = I[c] M[idx][y] += 1 C = [0, 0, 1, 1, 0, 0, 0, 1, 1] for y in range(9): M[y][7] = C[y] M[y][8] = C[y] M = pow_mat([[1 if i == j else 0 for j in range(9)] for i in range(9)], M, n) X = mat_mul(M, [1, 0, 0, 0, 0, 0, 0, 0, 0]) return X[-2] for _ in range(int(input())): print(main())