結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
|
提出日時 | 2025-08-22 23:18:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,097 ms / 2,000 ms |
コード長 | 1,186 bytes |
コンパイル時間 | 520 ms |
コンパイル使用メモリ | 82,604 KB |
実行使用メモリ | 78,508 KB |
最終ジャッジ日時 | 2025-08-22 23:18:24 |
合計ジャッジ時間 | 3,827 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
def matmul(a, b): n = len(a) c = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): for k in range(n): c[i][j] += a[i][k] * b[k][j] c[i][j] %= 998244353 return c def matpow(A, k): res = [[int(i == j) for j in range(len(A))] for i in range(len(A))] p = A while k: if k & 1: res = matmul(res, p) p = matmul(p, p) k >>= 1 return res T = int(input()) for _ in range(T): n = int(input()) state = [1, -1, 2, -2, 4, -4, -8, 1, -1] select = [1, -1, 2, -2] sz = len(state) mat = [[0] * sz for _ in range(sz)] for i in range(sz): for y in select: x = state[i] z = x * y if z == 8: j = 0 elif z not in state: continue elif 7 <= i and z == 1: j = 7 elif 7 <= i and z == -1: j = 8 else: j = state.index(z) mat[i][j] += 1 """ for line in mat: print(line) print("-" * 30) """ res = matpow(mat, n) print(res[7][0])