結果
| 問題 | No.3809 Count Bipartite Permutations |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-15 17:49:36 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
RE
不安定
|
| 実行時間 | - |
| コード長 | 2,532 bytes |
| 記録 | |
| コンパイル時間 | 88 ms |
| コンパイル使用メモリ | 64,108 KB |
| 実行使用メモリ | 1,332,216 KB |
| 最終ジャッジ日時 | 2026-11-20 20:53:43 |
| 合計ジャッジ時間 | 4,577 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge3_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 RE * 2 MLE * 2 -- * 8 |
ソースコード
# 誤解法4 (MLE): 和の配列を K+1 の長さで確保している。K = 10^9 でメモリが足りない
# 答え = N! * (1..2N の完全マッチングのうち、各ペアの最小値の和が K のものの個数)
# 1..2N を小さい順に見て、
# dp[j][s] = 相手待ちが j 個、最小値 (= 上段に置く値) の和が s である場合の数
# x を開く : (j, s) -> (j+1, s+x)
# x で閉じる: (j, s) -> (j-1, s) 相手の選び方が j 通り
# 高速化のため、各 (x, j) で「到達可能」かつ「最終的に和 K に届きうる」
# s の区間だけを計算する
import sys
MOD = 998244353
def main():
N, K = map(int, sys.stdin.read().split())
M = K # 誤り: 和は K までしか要らないと考えて K+1 で確保 (正しくは N*N で十分)
if K < N * (N + 1) // 2:
print(0)
return
def window(x, j):
# x 個処理済み・待ち j 個のときに計算が必要な s の区間 [L, R]
a, c = (x + j) // 2, (x - j) // 2 # これまでの open 数 / close 数
lo = a * (a + 1) // 2 # 1..a を open したとき
hi = c * c + (2 * c + 1 + x) * j // 2 # 交互に open/close して最後に j 個 open
o = (2 * N - x - j) // 2 # 今後の open 数
fmin = o * x + o * (o + 1) // 2 # x+1..x+o を open
fmax = o * (x + j + 1) + o * (o - 1) # j 個閉じてから交互に open/close
return max(lo, K - fmax), min(hi, K - fmin)
def seg(row, l, r):
# row[l..r] を返す (l < 0 の部分は 0 埋め)
if l < 0:
return [0] * (-l) + row[0:r + 1]
return row[l:r + 1]
ZERO = [0] * (M + 1)
dp = [ZERO] * (N + 2)
dp[0] = [0] * (M + 1)
dp[0][0] = 1
for x in range(1, 2 * N + 1):
nd = [ZERO] * (N + 2)
for j in range(x % 2, min(x, 2 * N - x) + 1, 2):
L, R = window(x, j)
if L > R:
continue
row = [0] * (M + 1)
B = dp[j + 1][L:R + 1] # close: (j+1) * dp[j+1][s]
m = j + 1
if j >= 1:
A = seg(dp[j - 1], L - x, R - x) # open: dp[j-1][s-x]
row[L:R + 1] = [(a + m * b) % MOD for a, b in zip(A, B)]
else:
row[L:R + 1] = [m * b % MOD for b in B]
nd[j] = row
dp = nd
f = 1
for i in range(1, N + 1):
f = f * i % MOD
print(dp[0][K] * f % MOD)
main()
sepa38