Codeforces Round #641 (Div. 1) F1. Slime and Sequences (Easy Version)

Problem - F1 - Codeforces

問題概要

※解説の都合上、0-indexedで表記します。

正整数 $n$ が与えられる。長さ $n$ の非負整数列 $p = \lbrace p_{0}, ..., p_{n-1}\rbrace$ が以下の性質を満たす時、これを「良い数列」であると呼ぶ。

$p$ に1つ以上含まれる任意の正整数 $k$ について、 $i \lt j$ かつ $p_{i} = k-1$ かつ $p_{j} = k$ であるインデックスの組 $(i, j)$ が存在する。

$v=0, ..., n-1$ のそれぞれに対して、全ての良い数列について値 $v$ が登場する個数の合計値を $\bmod 998244353$ で求めよ。

制約

$1 \le n \le 5000$

解法

全単射の構成とその証明

公式解説の初手が天才なので天下りの書き方になってしまいますが、良い数列を以下のように長さ $n$ の順列と一対一対応させます。

順列 $q = \lbrace q_{0}, ..., q_{n-1}\rbrace$ について、隣り合う要素の間に大小関係に応じて > または < を書き込む。
$a_{j}$ を「上記手順で $q_{j}$ よりも左側にある < の個数」と定義する。このとき $a = \lbrace a_{0}, ..., a_{n-1}\rbrace$ は隣り合う要素の差が $0$ または $1$ の広義単調増加数列となる。
$p_{q_{j}} = a_{j}$ となるように数列 $p$ を構成する。

これが良い数列と正しく一対一対応している（全単射になっている）ことを証明します。以降の証明では、 $q$ と $a$ のインデックスを $j$ 、 $p$ のインデックスを $i$ と表記しています。

順列→良い数列

順列から数列は一意に構成されるので、構成されたものが良い数列であることを示します。

順列 $q$ に書き込んだ < のうち、左から $k$ 番目（ $k$ は $1$ 始まり）にある < を挟む2要素を考え、これらのインデックスを $j, j+1$ とします。このとき < が書かれていることから $q_{j} \lt q_{j+1}$ であり、かつ $a$ の決め方から $a_{j} = k-1$ と $a_{j+1} = k$ です。よって $(q_{j}, q_{j+1})$ がそのまま良い数列を満たす条件に合う $p$ のインデックスの組になります。

全ての < の個数は $a_{n-1} = \max p_{i}$ に一致し、 $k=1, ..., a_{n-1}$ の全てについて上記が成り立つので、 $p$ は良い数列です。

良い数列→順列

良い数列から元の順列が一意に復元できることを示します。

まずは中間の数列 $a$ を復元します。順列から生成される $a$ は広義単調増加なので、これは即ち $p$ をソートしたものになります。

ここで $p$ に値 $k$ が複数含まれる場合、 $p_{i} = k$ である $i$ たちと、 $a_{j} = k$ である $q_{j}$ たちがどう対応するかの選択肢があります。しかし不等号の条件に矛盾しないようにするとこの対応は一意に定まります。具体的には $a_{j}$ として同じ値が並んでいるゾーンで < が出現してはいけないので、 $q_{j}$ はこのゾーン内で降順になっている必要があります。

そして降順になるように割り当てた場合、左から $k$ 番目の < を挟む箇所に存在している $q$ の要素を $q_{j}, q_{j+1}$ とすると、これは「 $p_{i} = k-1$ である $i$ の最小値」と「 $p_{i} = k$ である $i$ の最大値」であり、 $p$ が良い数列であることから必ず $q_{j} \lt q_{j+1}$ となります。