結果
問題 |
No.3176 転移迷宮 (Hard)
|
ユーザー |
|
提出日時 | 2025-02-20 19:34:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,952 ms / 3,000 ms |
コード長 | 1,410 bytes |
コンパイル時間 | 941 ms |
コンパイル使用メモリ | 81,912 KB |
実行使用メモリ | 165,560 KB |
最終ジャッジ日時 | 2025-02-20 20:56:12 |
合計ジャッジ時間 | 42,015 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
T = int(input()) for testcase in range(T): # 入力を受け取る N, K = map(int, input().split()) siz = 2 * K + 1 # 行列を生成 A = [[-1 for j in range(siz)] for i in range(N)] for i in range(N): A[i][K] = 2 * K for j in range(0, K - i): A[i][j] = 0 A[N - 1 - i][2 * K - j] = 0 # 右辺を生成 ans = [siz] * N # ガウスの消去法を実行 for rank in range(N): # A[rank][K] を 1 にする処理 div = pow(A[rank][K], -1, 998244353) for j in range(K, siz): A[rank][j] *= div A[rank][j] %= 998244353 ans[rank] *= div ans[rank] %= 998244353 # A[rank + i][K - i] において非ゼロの成分を削除する処理 for i in range(1, K + 1): if rank + i >= N: break coef = A[rank + i][K - i] ans[rank + i] -= coef * ans[rank] ans[rank + i] %= 998244353 for j in range(K, siz): A[rank + i][j - i] -= coef * A[rank][j] A[rank + i][j - i] %= 998244353 # 後退代入 for i in range(N - 2, -1, -1): for j in range(1, K + 1): if i + j >= N: break ans[i] -= A[i][K + j] * ans[i + j] ans[i] %= 998244353 # 答えを出力 print(*ans)