In this problem, out of the \(N\!\) ways to rearrange the elements of \(A\) (distinguishing the same value), you are asked to find the number of those such that there are \(K\) indices \(i\) such that \(A_i \lt A_{i + 1}\).

Consider arranging the smaller elements first. Starting from \(a = (0, 0)\), we will insert each element to one of \((|a|-1)\) spots.
For example, when we rearrange \(A = (1, 2, 3)\) to obtain \((2, 3, 1)\), \(a\) is constructed as follows:

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

In \(a = (a_1, \dots, a_{N + 2})\) after rearranging all elements, we always have \(a_1 \lt a_2, a_{N + 1} \gt a_{N + 2}\), so what we want is the number of ways to have exactly \((K+1)\) indices \(i\) such that \(a_i \lt a_{i + 1}\).

Consider inserting \(x\) to \(a = (a_1, \dots, a_n)\) anew. The elements of \(a\) is all less than or equal to \(x\). The number of \(i\)’s such that \(a_i \lt a_{i + 1}\) increases by \(1\), or does not increase at all; it increases if:

• \(x\) is inserted between \(a_i\) and \(a_{i+1}\) such that \(x \gt a_i \geq a_{i + 1}\).

We want to remove the positions where \(x = a_i\) from those where \(a_i \geq a_{i + 1}\), so the number of such \(i\)’s can be found by managing the number of \(i\)’s such that \(a_i \lt a_{i + 1}\).

Therefore, the problem can be solved in a total of \(O(NK)\) time with the following DP:

• \(\mathrm{dp}_{n, m} := \) the number of rearrangements of the smallest \(n\) elements such that there are \(m\) indices \(i\) such that \(a_{i} \lt a_{i + 1}\).

Sample code (C++)

By the way, if \(A_i\) are distinct in this problem, the desired count equals the number of permutations such that there are \(K\) indices \(i\) such that \(P_i \lt P_{i + 1}\). Such number is called Eulerian number, which is known to be able to computed in an \(O(N)\) time.