条件の言い換え

数列 \(A,B\) について、\(B\) が \(A\) の部分列であることを \(B\prec A\) で表すことにします。 また、数列 \((x_1,\dots,x_m)\) について、問題文中の長さ以外の条件を満たす数列の集合を \(f((x_1,\dots,x_m))\) と表します。 つまり、

\[ f((x_1,\dots,x_m)) = \{a \in \{1,\dots, K\}^* \mid \forall b \in \{1,\dots, K\}^m ~ b\prec a \iff b\neq (x_1,\dots,x_m)\} \]

です。\(f((x_1,\dots,x_m))\) の元は、長さが \(m\) より短い任意の数列を部分列として持つことに注意してください。

\(X_1=X_2\) の場合

まず、\(X_1=X_2\) の場合に \((A_1,\dots,A_N)\in f((X_1,\dots,X_M))\) であるために必要な条件を列挙していきます。

\((A_1,\dots,A_N)\) に最初に出てくる \(X_1\) の位置を \(i\) とします（存在しない場合は条件を満たしません）。このとき、以下が必要です。

1. \((A_{i+1},\dots,A_N)\in f((X_2,\dots,X_M))\)
2. \(A_1,\dots,A_{i-1}\) には \(X_1\) 以外のすべてが現れる

2が必要であることを確認するために、初出が \(X_1\) よりも遅い数 \(s\) が存在する場合を考えます。\(s\) が最初に出てくる位置を \(j\) とおきます(\(i<j\))。1より、\((X_2,\dots,X_M) \nprec (A_{i+1},\dots,A_{j+1},\dots,A_N)\) なので当然、\((X_2,\dots,X_M) \nprec (A_{j+1},\dots,A_N)\) であることから、\((s,X_2,\dots,X_M) \nprec (A_1,\dots,A_N)\) となってしまいます。

この \(2\) つの条件が十分条件にもなっていることを確認します。

\((X_1,X_2,\dots,X_M) \nprec (A_1,\dots,A_N)\) は1から直ちに従います。同様に、\((X'_2,\dots,X'_M)\neq(X_2,\dots,X_M)\) について\((X_1,X'_2,\dots,X'_M)\prec (A_1,\dots,A_N)\) であることも1から分かります。 あとは \(X'_1\neq X_1\) であるときに \((X'_1,X_2,\dots,X_M) \prec (A_1,\dots,A_N)\) が言えればよいです。2から、\((X'_1,X_2)\prec (A_1,\dots,A_i)\) です。また、1より、\((X_3,\dots,X_M)\) の長さが \(M-1\) より短いことから、 \((X_3,\dots,X_M)\prec (A_{i+1},\dots,A_N)\) です。よって、 \((X'_1,X_2,\dots,X_M) \prec (A_1,\dots,A_N)\) です。

\(X_1\neq X_2\) の場合

\(X_1\neq X_2\) の場合も同様に \((A_1,\dots,A_N)\in f((X_1,\dots,X_M))\) であるために必要な条件を列挙していきます。

\((A_1,\dots,A_N)\) に最初に出てくる \(X_1\) の位置を \(i\) とすると、先程と同様に以下が必要です。

1. \((A_{i+1},\dots,A_N)\in f((X_2,\dots,X_M))\)

2. \(A_1,\dots,A_{i-1}\) には \(X_1\) 以外のすべてが現れる

   また、\((A_1,\dots,A_{i+1})\) に最後に出てくる \(X_2\) の位置を \(j\) とすると、以下も必要です。

3. \(A_1,\dots,A_{j-1}\) には \(X_1\) 以外のすべてが現れる

3が必要であることを確認するために、\(s\neq X_1\) が \(A_1,\dots,A_{j-1}\) に現れない場合を考えます。\(s\) が最初に出てくる位置を \(k\) とすると、2より、\(j<k<i\) です。\(j\) の取り方から \(A_{k+1},\dots,A_{i}\) に \(X_2\) は存在しないので、\((s,X_2,\dots,X_M)\prec (A_1,\dots,A_N) \iff (X_2,\dots,X_M)\prec (A_{i+1},\dots,A_N) \) ですが、1より、\((X,X_2,\dots,X_M)\nprec (A_1,\dots,A_N) \) となってしまいます。

この \(3\) つの条件が十分条件にもなっていることは先程と同様に確認できます。

動的計画法

長さ \(n\) の数列のうち \(f((X_k,\dots,X_M))\) の元になるものの数を dp[k][n] とします。上記のどちらの場合でも1の条件があることから、\(k,n,i\) について dp[k][n+i] += hoge * dp[k+1][n] のようにテーブルを更新していけます。この係数の hoge の部分を求めていきます。

\(X_k=X_{k+1}\) の場合

上記の必要十分条件より、長さ \(i-1\) の数列であって、ちょうど \(K-1\) 種類の数を使う数列の数を係数とすればよいです。これは、各 \(i\) について包除原理で \(O(K)\) で求めることができるので、\(O(NK)\) の前計算をすればよいです。

\(X_{k}\neq X_{k+1}\) の場合

必要十分条件を整理すると、以下のようになります。

• 最初の \(j-1\) 項にはちょうど \(K-1\) 種類が現れる
• \(j\) 項目は \(X_{k+1}\)
• \(j+1\) 項目から \(i-1\) 項目までは \(X_{k},X_{k+1}\) 以外ならなんでもよい
• \(i\) 項目は \(X_i\)

よって、\(X_k=X_{k+1}\) の場合で前計算した数列に \(((K-2)^0, (K-2)^1, \dots,)\) という数列を畳み込んだものを前計算すれば良く、 \(O(N^2)\) でできます。

全体では \(O(N^2M + NK)\) となり、十分高速です。

C++による実装例