結果
問題 |
No.3243 Multiplication 8 1
|
ユーザー |
👑 |
提出日時 | 2025-08-22 23:06:54 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,016 bytes |
コンパイル時間 | 407 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 83,068 KB |
最終ジャッジ日時 | 2025-08-22 23:07:03 |
合計ジャッジ時間 | 8,511 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 TLE * 2 |
ソースコード
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] ans -= multiply_vector(power(Y, N), [1])[0] print(ans % MOD) if __name__ == "__main__": T = int(input()) for _ in range(T): solve()