結果
問題 |
No.3176 転移迷宮 (Hard)
|
ユーザー |
|
提出日時 | 2025-06-06 23:50:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,923 ms / 3,000 ms |
コード長 | 1,424 bytes |
コンパイル時間 | 1,156 ms |
コンパイル使用メモリ | 82,332 KB |
実行使用メモリ | 168,576 KB |
最終ジャッジ日時 | 2025-06-06 23:51:36 |
合計ジャッジ時間 | 46,521 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
import sys input = lambda :sys.stdin.readline()[:-1] ni = lambda :int(input()) na = lambda :list(map(int,input().split())) yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES") no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO") ####################################################################### mod = 998244353 for _ in range(ni()): n, k = na() m2 = pow(k * 2, mod-2, mod) a = [[-1] * (2 * k + 1) for i in range(n)] v = [2 * k + 1] * n for i in range(n): a[i][k] = k * 2 for i in range(n): inv = pow(a[i][k], mod-2, mod) v[i] *= inv v[i] %= mod for x in range(k * 2 + 1): a[i][x] *= inv a[i][x] %= mod for j in range(1,k+1): if i + j >= n: break mul = a[i + j][k - j] # a[i][x] -> a[i + j][x - j] v[i + j] -= v[i] * mul % mod v[i + j] %= mod for x in range(j, 2 * k + 1): a[i+j][x-j] -= a[i][x] * mul % mod a[i+j][x-j] %= mod # for i in range(n): # print(a[i]) ans = [0] * (n + k) for i in range(n-1, -1, -1): ans[i] = v[i] for j in range(k + 1, k * 2 + 1): # print(i, j, i + j - k) ans[i] -= ans[i + j - k] * a[i][j] % mod ans[i] %= mod print(*ans[:n])