結果
| 問題 | No.3809 Count Bipartite Permutations |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-09-21 11:03:31 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,749 ms / 2,000 ms |
| + 741µs | |
| コード長 | 749 bytes |
| 記録 | |
| コンパイル時間 | 94 ms |
| コンパイル使用メモリ | 64,144 KB |
| 実行使用メモリ | 712,380 KB |
| 最終ジャッジ日時 | 2026-11-20 20:51:45 |
| 合計ジャッジ時間 | 19,851 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
ソースコード
n, k = map(int, input().split())
# k の上限は、1 + 3 + 5 + ... + 2*n-1 = n*(n+1) - n = n*n
k = min(k, n*n+1)
mod = 998244353
dp = [[[0]*(k+1) for _ in range(n+1)] for _ in range(2*n+1)]
# dp[i][j][l]: i 番目まで見て、左半分に j 個置いて、左半分の和が l
# dp[0][0][0] = 1
dp[1][1][1] = n # 1 は左半分に置くしかない
for i in range(1, 2*n):
for j in range(n+1):
for l in range(k+1):
dp[i][j][l] %= mod
# 右に置く
dp[i+1][j][l] += dp[i][j][l] * (j*2 - i) % mod
if j + 1 <= n and l + i + 1 <= k: # 左に置く
dp[i+1][j+1][l+i+1] += dp[i][j][l] * (n - j) % mod
# print(*dp[i])
# print(*dp[2*n])
print(dp[2*n][n][k] % mod)
sepa38