結果
問題 | No.2529 Treasure Hunter |
ユーザー |
![]() |
提出日時 | 2023-11-25 02:58:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 152 ms / 2,000 ms |
コード長 | 555 bytes |
コンパイル時間 | 361 ms |
コンパイル使用メモリ | 82,600 KB |
実行使用メモリ | 96,160 KB |
最終ジャッジ日時 | 2024-09-26 10:10:15 |
合計ジャッジ時間 | 3,621 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
mod = 998244353 def solve(): N,M = map(int,input().split()) dp = [[0,0,0] for i in range(M+1)] dp[0][0] = 1 a = N*(N-1)//2 - N a %= mod b = a - N + 3 b %= mod c = a - 2*N + 7 c %= mod if N <= 3: a = b = c = 0 for i in range(M): dp[i+1][0] = sum(dp[i]) dp[i+1][0] %= mod dp[i+1][1] = dp[i][0]*N + dp[i][1]*(N-1) + dp[i][2]*(N-2) dp[i+1][1] %= mod dp[i+1][2] = dp[i][0]*a + dp[i][1]*b + dp[i][2]*c dp[i+1][2] %= mod ans = sum(dp[M]) ans %= mod print(ans) t = int(input()) for _ in range(t): solve()