AtCoder Regular Contest 100 F - Colorful Sequences

問題

https://beta.atcoder.jp/contests/arc100/tasks/arc100_d

解法

「全ての列についての $A$ に一致する連続する部分列の個数の総和」から「カラフルでない列についての $A$ に一致する連続する部分列の個数の総和」を引く方針で考えます。前者は簡単なので省略します。後者は $A$ がカラフルな場合は $0$ なので、以下カラフルでないものとします。
まず次のDPを考えます。

$dp[i][j]=$ ある特定の長さ $i$ のdistinctな列の後に、 $j$ 個の要素を繋げてできるカラフルな列の個数

次が成り立ちます。

$dp[i][j]=\displaystyle \frac {dp[i-1][j+1] - \displaystyle \sum_{i'=1}^{i-1} dp[i'][j]} {K-i+1}$

ただし、このDPを初期化するには、 $dp[1][j]$ が分かっていないといけません。そこで、

$dp'[j][k]=$ ある特定の $1$ 項の後に、 $j$ 個の要素を繋げてできるカラフルな列であって、distinctなsuffixの最大長さが $k$ であるものの数

というものを考えれば、

$dp'[j][k]=\displaystyle \sum_{k'=k}^{K-1} dp'[j-1][k']+(K-k+1)dp'[j-1][k-1]$

と遷移が定義できることがわかります。 $dp[1][j]=dp'[j+1][1]$ です。これらのDPはいずれも累積和で高速化できます。
さて、以上を使って「カラフルでない列についての $A$ に一致する連続する部分列の個数の総和」を求めていきましょう。
$A$ がdistinctな場合。数列中に長さ $M$ のdistinctな列が登場する場合の数は、終了位置を $j$ と固定すれば、 $K \sum_{k=M}^{K-1} dp'[j-1][k]dp[k][N-j]$ です。その中に、 $A$ はちょうど $\frac{(K-M)!}{K!}$ の割合で存在します。あとは $j$ を $M$ から $N$ まで動かして総和をとればよいです。
$A$ がdistinctでない場合。 $A$ のdistinctなprefixの最大長さを $l$ 、suffixの最大長さを $r$ とすると、数列中に $A$ が登場する場合の数は、開始位置を $i$ と固定すれば、 $dp[i-1][l]dp[N-M-i][r]$ になります。あとは $i$ を $1$ から $N-M$ まで動かして総和をとればよいです。
計算量は全体で $O(NK)$ になります。