結果

問題 No.3809 Count Bipartite Permutations
コンテスト
ユーザー sepa38
提出日時 2026-11-15 17:48:02
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,543 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 96 ms
コンパイル使用メモリ 64,228 KB
実行使用メモリ 95,896 KB
最終ジャッジ日時 2026-11-20 20:53:37
合計ジャッジ時間 3,567 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge1_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 27 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# 誤解法1 (WA): 和の上限の判定が off-by-one (K >= N*N で 0 にしてしまう)。K = N^2 で誤答
# 答え = 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 = N * N  # 最小値の和の最大値 (ペア (1,2),(3,4),... のとき)
    if K >= M or K < N * (N + 1) // 2:  # 誤り: 正しくは K > M
        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()
0