Day 162-Q4 — 2026-09-27 — 転倒数がちょうど K の順列を数える（挿入 DP の遷移を累積和で O(1) にする）

問題

$1,2,\dots,N$ の順列 $p$ のうち、転倒数（$i<j$ かつ $p_i>p_j$ となる組 $(i,j)$ の個数）がちょうど $K$ であるものの個数を $998244353$ で割った余りを求めよ。

入力形式

N K

制約

入出力例

3 1

2

（転倒数 1 の順列は $(2,1,3)$ と $(1,3,2)$）

4 3

6

10 20

230131

1000 10000

507792345

背景と出典

概念図：差し込みと窓の和

ヒント（クリックで段階的に開示）

模範解答 (Python)

📋 コピーimport sys
from itertools import accumulate
from operator import sub

MOD = 998244353


def main():
    n, K = map(int, sys.stdin.readline().split())
    if K > n * (n - 1) // 2:
        print(0)
        return
    dp = [1]                                   # 長さ 1 の順列: 転倒数 0 が 1 通り
    for i in range(2, n + 1):
        # 新しい最大値 i を差し込む位置で、転倒数が 0..i-1 のどれか 1 つだけ増える
        top = min(K, i * (i - 1) // 2)         # K を超える転倒数は答えに効かない
        L = len(dp)
        S = [0]
        S += accumulate(dp)                    # S[t] = dp[0] + ... + dp[t-1]
        # new[k] = dp[max(0,k-i+1)] + ... + dp[min(k,L-1)] = hi[k] - lo[k]
        hi = S[1:] + [S[L]] * (top + 1 - L)    # S[min(k+1, L)]
        lo = [0] * (i - 1) + S[:top + 2 - i]   # S[max(0, k-i+1)]
        dp = [x % MOD for x in map(sub, hi[:top + 1], lo[:top + 1])]
    print(dp[K])


main()

Step-by-Step 解説

迷った他案と採らなかった理由

前提が変わったら:

• $K\le N$ で $N$ が巨大（例 $N=10^{18}$）なら、$\prod_{i=1}^{N}(1-x^i)$ の $x^K$ までの係数は $\prod_{i\ge1}(1-x^i)$ と同じで、Euler の五角数定理から $\pm1$ が $O(\sqrt K)$ 個だけ立つ。答えは
  $$\sum_{t}e_t\binom{N-1+K-t}{K-t}$$
  （$e_t$ は五角数 $t=j(3j\mp1)/2$ で $(-1)^j$）。$N\le58$・$K\le N$ の 610 組で本解の DP と全件一致し、$N=10^{18},K=10^4$ が 0.16 s（実測）。Day156 Q2 の五角数定理と同じ道具
• $N$ が大きく $K$ も大きい（$N,K\sim10^5$）なら $O(NK)$ は無理。母関数を FPS の log/exp で扱う（M3 の範囲）
• 法が素数でない なら累積和の差はそのまま使える（割り算が無い）が、五角数の別解は二項係数の逆元が要るので使えない

よくあるミス

次のステップ

• 発展1: 転倒数が $K$ 以下 の順列の個数（最後に累積和を 1 回取るだけ）
• 発展2: 「$p_i>p_{i+1}$ となる位置（降下）がちょうど $K$ 個」の順列＝Euler 数 $\langle{N\atop K}\rangle$。挿入 DP の遷移が変わる（Day161 Q3 の挿入 DP と比べる）
• 次回予告: 不等式の連立を最短路で解く（牛ゲー）→ Q5

自己評価

自分の回答

気づき・メモ