公式解説とほぼ同じです。（公式解説では \(1\) つずつ値を追加していますが、ここでは、同じ値は同時に追加することを考えます。これにより、\(x=a_i\) のケースを考える必要がなくなります）

空の数列 \(a=()\) から始め、\(A\) の要素を小さい順に追加するDPを考えます。ただし、同じ値は同時に追加します。つまり、\(A=(1,1,2,3,3,3)\) であれば、

• \(2\) 個の \(1\) を追加する
• \(1\) 個の \(2\) を追加する
• \(3\) 個の \(3\) を追加する

の \(3\) ステップで要素の追加を行うという意味です。

DPテーブルの定義は次の通りです。

\(\mathrm{dp}_{n, m} := \) 小さい方から \(n\) 個の要素を追加して、\(a_{i} \lt a_{i + 1}\) となる \(i\) が \(m\) 個であるようにする方法の総数。

\(a=(a_1,\ldots,a_n)\) に新たに \(v\) を \(x\) 個追加するとします。数列の末尾か \(a_i\geq a_{i+1}\) となるような \(a_i\) と \(a_{i+1}\) の間に \(v\) を \(1\) 個以上追加するごとに、追加後の数列には \(a_i< a_{i+1}\) となる箇所の個数は増えます。
そこで、そのような箇所を \(k\) 個選ぶとします。\(v\) を追加できるのは、選んだ箇所と、数列の先頭か \(a_i<a_{i+1}\) となるような \(a_i\) と \(a_{i+1}\) の間です。

• \(k\) 箇所の選び方が \(\binom{n-m}{k}\) 通り
• 選んだ \(k\) 箇所に \(1\) 個以上、それ以外の割り当て可能な箇所に \(0\) 個以上の \(v\) を割り当てる方法が \(\binom{x+m}{x-k}\) 通り
• 追加する \(x\) 個の \(v\) の並び替えが \(x!\) 通り

以上をあわせて、\({\rm dp}_{n,m}\) から \({\rm dp}_{n+x,m+k}\) への遷移にかかる係数は \(\binom{n-m}{k}\binom{x+m}{x-k}x!\) となります。遷移先は \(0\leq k\leq x\) の全ての \(k\) です。

二項係数を前計算することで \(O(NK)\) で解けます。（各 \(m\) について、\({\rm dp}_{*,m}\) からの遷移の合計が \(O(\sum x)=O(N)\) であるため）

実装例(C++)

類題：TDPC O『文字列』