ABC267 G - Increasing K Times の計算量について - 輪郭をなぞるだけのブログ

解説見ても計算量について理解できなかったので、自分なりに考えたものの備忘録。

問題

長さ $N$ の整数列 $A$ が与えられる。
これを並び替えた数列を $B$ として、次の条件を満たすものの総数を $998244353$ で割った余りを求める。ただし、重複する要素は区別する。
・ $B_{i} < B_{i+1}$ となる $i$ の個数がちょうど $K$ 個である。 $(0 \leq i \leq N-1)$

制約

$2 \leq N \leq 5000$
$0 \leq K \leq N - 1$
$1 \leq A_{i} \leq N$

計算量

DP を次のように定義して、 $A$ の要素昇順で並べ方を決める。
$dp_{n, m} :=$ $n$ 個並べているときの、 $B_{i} < B_{i+1}$ となる $i$ の個数がちょうど $m$ 個である並べ方

まず、 $A$ の要素がすべて異なる distinct である状態を考える。
このとき、DP テーブルの各マスからの遷移は高々 $2$ 通りであり、計算量は $O(N^{2})$ となる。( 下図参照 )

次に、重複する要素が存在する場合を考える。
distinct であるときの遷移からどう変化するのかを考えてみる。
$n$ 個並べた数列に新しく追加する要素が $1$ 個から $2$ 個に増えたとする。
( 一例を下に示す。)

distinct では $n$ 行目から $n+1$ 行目への遷移だったものが、 $n$ 行目から $n+2$ 行目への遷移となる。
このとき、distinct であるときの $n+1$ 行目から $n+2$ 行目への遷移に必要な計算 (最大 $2(n+1)$ 回) がなくなり、 $n$ 行目からの遷移は各マスについて高々 $1$ 回増える。
ゆえに、重複する要素が発生しても、distinct であるときと比べて計算回数は増えない。
重複が $3$ 個以上になっても、 $1$ 個ずつ重複する要素が増えると考えて、おそらく同じことが言える。