包除原理を用いても解くことができます。

長さ \(N\) のカラフルな数列はいくつか？

まず、この問題を \(1, \ldots, K\) の並び替えを連続部分列として含む個数について包除原理を適用することで数えます。この数をカラフル数と呼ぶことにします。

次のような DP を考えます。

• \(dp[i] := [i, i + k)\) が \(1, \ldots, K\) の並び替えになっている数列について、の \((-1)^{カラフル数}\) の和

これは次のように遷移することがわかります。

• \(dp[i] = K^i * K!\) 　(初期値)
• \(dp[i + j] = dp[i + j] - dp[i] * j!\)　\((1 \le j < K)\)
• \(dp[i + j] = dp[i + j] - dp[i] * K! * K ^ {j - K}\)　\((K \le j)\)

これは、累積和を用いることで \(O(NK)\) で処理することができます。

この \(DP\) を用いて元の問題を解きます。

\(A\) に \(1, \ldots, K\) の並び替えが連続部分列として含まれる場合

答えは \(K ^ {N - M} * (N - M + 1)\) です。

上記以外で、\(A\) に重複がある場合

上の DP において、\([i, i + M)\) が \(A\) に一致するという制限をかけます。すると、重複があり連続部分列に \(1, \ldots , K\) の並び替えを含まないことから、カラフル数を最後に数えた場所は左側と右側両方について \(A\) の境界を越さず、干渉しあわないことがわかります。

よって、最後に数えた部分列の位置ごとに適切な係数を掛けることで、\([i, i + M)\) が \(A\) に一致するときの場合の数を累積和を用いて \(O(K)\) で求められます。

\(i\) を全ての候補について試しても、計算量は \(O(NK)\) です。

重複がない場合

上記の干渉しあわないパターンに加えて、 \([l , l + K)\)　\( \left( l < i, i + M < l + K\right)\) を満たすような\([l, l + K)\) をカラフル数として数えている場合についても考える必要があります。(\(A\) を完全に覆っているパターン)

カラフル数として数えた \(A\) を完全に覆っている部分列のうち、最も左側のものを固定して数え上げます。これをするには DP の 2 つめ、3 つめの遷移を途中で止める必要がありますが、毎回このパターンを数えるときに遷移を進めて巻き戻しても結局計算量は \(O(NK)\) で変わりません。