We first find out the no. of distinct no.s and their frequency in the array. Let us denote this Frequency array by F. We do this because we need to find all sorted the sequences of length K. So we can approach this problem by thinking how many occurrences of some particular distinct element will we pick in a particular sequence for each distinct element. After this is decided the no. of ways of obtaining this sequence is the summation of ( factorial(no. of elements you picked of ith distinct element)) for all distinct elements. For eg, you have an array 1 2 2 and K=3, so you have 2 occurrences of 2 and 1 occurrence of 1. so no. of ways of obtaining a valid sequence is 1! * 2!.
After that, we create an array DP[ i ][ j ] where the ith state denotes the index of the distinct no. we are on and j represents the no. elements that have been picked by us. we approach this DP in a top-down fashion and for any particular state, we find its value by taking the summation of all values obtained if xth occurrences of the ith distinct element are picked. Refer to my solution for More clarity as its well commented for your ease.
You can actually solve this problem for all k \le n in \mathcal{O}(n \log^2 n).
First we use index compression so that 0\le A_i < r where r \le n is the total number of distinct elements in the array.
Now let n_j be the number of occurrences of j in A. Note that \sum_{0 \le j < r} n_j = n.
Now the problem asks us to find the total number of non-decreasing sequences of length k.
We use the notation \binom{n}{r} = ^n\hspace{-0.25 em}C_r and \binom{n}{r} = 0 if r < 0 or r > n.
If we construct a sequence of length k by picking the number j, k_j times (\sum_{0 \le j < r} k_j = k), the number of non-decreasing sequences of this form will be \prod_{0 \le j < r} k_j ! \binom{n_j}{k_j}.
Summing this over all possible k_j's we get the answer to be \displaystyle \sum_{k = \sum_{0 \le j < r} k_j} \prod_{0 \le j < r} k_j ! \binom{n_j}{k_j}, let’s call this f(k) for convenience.
Also for convenience call f_j(b) = b! \binom{n_j}{b}, ie, \displaystyle f(k) = \sum_{k = \sum_{0 \le j < r} k_j} \prod_{0 \le j < r} f_j(k_j)
Now let polynomials P_j(x) = \sum_{0\le i \le n_j} f_j(i) x^i and P(x) = \sum_{0 \le i \le n} f(i) x^i.
You can show that \displaystyle P(x) = \prod_{0 \le j < r} P_j(x).
We can easily compute all the coefficients of P_j(x) in linear time by precomputing all factorials.
Thus, now all we need to do is multiply these polynomials. If you use divide and conquer + FFT, the polynomials can be multiplied in \mathcal{O}(n \log^2 n).
If rather than using FFT we use naive multiplication the time complexity will be \mathcal{O}(n^2).