結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
👑 |
提出日時 | 2025-08-22 23:03:52 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,149 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 82,512 KB |
最終ジャッジ日時 | 2025-08-22 23:04:02 |
合計ジャッジ時間 | 6,616 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 3 TLE * 1 |
ソースコード
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) # print("X---") # print(*power(X, N), sep="\n") # print("Y---") # print(*power(Y, N), sep="\n") if __name__ == "__main__": T = int(input()) for _ in range(T): solve()