結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
👑 |
提出日時 | 2025-08-22 23:02:07 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,485 bytes |
コンパイル時間 | 354 ms |
コンパイル使用メモリ | 82,548 KB |
実行使用メモリ | 91,832 KB |
最終ジャッジ日時 | 2025-08-22 23:02:24 |
合計ジャッジ時間 | 5,971 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 1 TLE * 2 -- * 1 |
ソースコード
MOD = 998244353 def power(A, e): result = [ [1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1], ] 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, 0, 0, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], ] 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, 0, 0, 0, 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()