ブログ名

競技プログラミングやお歌のお話をする高菜です。

ARC 100 F - Colorful Sequence

ARC 100 F - Colorful Sequence

定義

${ 1, \dots, i }$ の要素からなる、要素の互いに異なる長さ $i$ の列を $i$ の置換と呼びます。 また数列に対して、その contiguous subsequence であって $i$ の置換であるようものが存在するとき、その数列は $i$ の置換を含むと呼びましょう。

$k$ 色のボールを重複を許して $n$ 個並べる並べ方と、 その連結な部分列であって $A$ に一致するものの組の集合を $X$ とおきましょう。 $X$ の要素数は $(n - m + 1) \cdot k ^ n$ です。

そのようなものの中で、$k$ の置換を含まないようなものの集合を $C$ とおきましょう。 すると、答えは差集合 $X \setminus C$ の要素数です。

前計算

このセクションでは $A$ は登場しませんし、結果も $A$ の中身には依存しません。 使うのは $n, k, m$ のみです。

前計算 1

長さ $i$ の列であって、$k$ の置換を含まないようなもので、  その longest unique suffix の長さが $j$ であるようなものの個数を $\mathtt { dp } _ { i, j }$ とおきます。

これは、次のように計算できます。 まず、$i = 0$ のときは、$j = 0$ ならば $1$、さもなくば $0$ です。 $i$ が $1$ 以上のときには、最後の文字が、それを追加する前の unique suffix を壊しているかどうかで $2$ 通りに場合分けされます。 $$ \mathtt{ dp } _ { i , j } = (k - (j - 1)) \cdot \mathtt{ dp } _ { i - 1, j - 1 } + \sum _ { j ' = j } ^ { k - 1 } \mathtt{ dp } _ { i - 1, j ' } $$

前計算 2

さて、今度は同じ条件を満たす列と、それの含む $m$ の置換組の個数を $\mathtt { ep } _ { i, j }$ とおきましょう。

これは件の $m$ の置換の位置が最後かどうかで場合分けです。 $A$ が最後に来るためには $j$ が $m$ 以上であることが必要十分ですから、そちらはそれを数えるとよいです。 一方最後以外に来るケースは、一つ短いものから $\mathtt { dp }$ と同じ遷移で伸ばして構成されるものですから、そのように遷移です。 $$ \mathtt{ ep } _ { i , j } = (k - (j - 1)) \cdot \mathtt{ ep } _ { i - 1, j - 1 } + \sum _ { j ' = j } ^ { k - 1 } \mathtt{ ep } _ { i - 1, j ' } \ \left(\ + \mathtt{ dp } _ { i, j } \mathtt{ if } \ m \le j \right ) $$

答え

場合分けです。

$A$ が contiguous unique subsequence of length $k$ を含んでいる場合

$0$ です。(この場合分けを忘れていてなかなか通りませんでした。)

$A$ が unique な場合

$C = \sum _ { j = 0 } ^ { k - 1 } \mathtt { ep } _ { n , j }$ です。

$A$ が unique でない場合

$A$ の場所が $[i, i + m[$ のときの個数を数えましょう。 $A$ の longest unique prefix, longest unique suffix の長さをそれぞれ $l, r$ とおいて、 $[0, i + l[, [(i + m) - r, n[$ に着目です。 $A$ 自体が $k$ の置換を含まないことから、全体が $k$ の置換を含んでいたとしても、それはこの $2$ つの区間のいずれかに含まれます。

まずは $[0, i + l[$ 文字までの様子を見てみます。これは長さ $i + l$ の数列で、$k$ の置換を含まず、最後の $l$ 文字が unique です。 しかしそういうものがなんでも当てはまるわけではなく、後ろ $l$ 文字は $A$ の prefix と一致していなければなりませんから、 個数は $k ^ { \underline { l } } \cdot \mathtt { dp } _ { i + l, l }$ です。

一方、$[(i + m) - r, n[$ は同様に長さ $n - (i + m) + r$ で、先頭 $r$ 個が unique です。さらに $A$ の suffix に一致しますから、 個数は $k ^ { \underline { r } } \cdot \mathtt { dp } _ { n - (i + m) + r, r }$ です。

これらを掛け算して足し合わせると良いです。 $$ C = \sum _ { i = 0 } ^ { n - m } k ^ { \underline { l } } \cdot \mathtt { dp } _ { i + l, l } \cdot k ^ { \underline { r } } \cdot \mathtt { dp } _ { n - (i + m) + r, r } $$