本問は、\(A\) の要素を (同じ値でも区別して) 並べ替える \(N!\) 通りの方法のうち、\(A_i \lt A_{i + 1}\) となる \(i\) が \(K\) 個になるようなものを数える問題です。

小さい順に要素を並べていくことを考えます。 \(a = (0, 0)\) から始め、先頭と末尾を除く \(|a| - 1\) 箇所のいずれかに要素を追加していくことにします。
例えば、\(A = (1, 2, 3)\) を並べ替えて \((2, 3, 1)\) とするとき、次のような手順で \(a\) を構成します。

\[(0, 0) \rightarrow (0, 1, 0) \rightarrow (0, 2, 1, 0) \rightarrow (0, 2, 3, 1, 0)\]

全ての要素を並べ終えた \(a = (a_1, \dots, a_{N + 2})\) において、必ず \(a_1 \lt a_2, a_{N + 1} \gt a_{N + 2}\) が成り立つので、求めるものは \(a_i \lt a_{i + 1}\) となる \(i\) をちょうど \(K+1\) 個にする方法の総数です。

\(a = (a_1, \dots, a_n)\) に新たに \(x\) を追加するとします。\(a\) の要素は全て \(x\) 以下です ( \(x\) と等しいこともあります)。\(a_i \lt a_{i + 1}\) となる \(i\) の個数は、\(1\) 増えるか全く増えないかのどちらかです。増えるのは次のような場合です。

• \(x \gt a_i \geq a_{i + 1}\) であるような \(a_i\) と \(a_{i+1}\) の間に \(x\) を追加する。

\(a_i \geq a_{i + 1}\) となる場所から \(x = a_i\) となる場所を除けばよいので、このような \(i\) の総数は \(a_i \lt a_{i + 1}\) となる \(i\) の個数を管理しておけば求めることができます。

よって、次のような動的計画法によって、この問題を \(O(NK)\) で解くことができます。

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

実装例 (C++)

余談ですが、本問で \(A_i\) が相異なる場合、すなわち \(P_i \lt P_{i + 1}\) となる \(i\) が \(K\) 個であるような順列の総数は Eulerian number と呼ばれ、\(O(N)\) で計算できることが知られています。