Given an array of first n natural numbers. Calculate number of total permutations with exactly k pairs satisfy the condition a[i]<a[j] and i<j.

Example — n = 3, k = 2

All permutations — [1,2,3][1,3,2][2,1,3][2,3,1][3,2,1][3,1,2]

Output — 2 ([2,1,3][1,3,2])

Check this. The solution to your problem is $$$\frac{n(n - 1)}{2} - S$$$ where $$$S$$$ is the number of inversions.

But above solution does not guarantee exactly k number of required pairs

Can it be solved using dp?

are you sure? check again

Yes

True

I don't know if there is a close formula, probably you can get something doing some algebra with generating functions, but since I haven't found anything I'll just explain a no brainer solution.

Notice that the generating function of the number of inversions is (1+$$$x$$$)(1+$$$x$$$+$$$x^2$$$)...(1+$$$x$$$+...+$$$x^{n-1}$$$).

Just use d&c NTT and output the $$$k$$$-th term in $$$O(n^2log^2n)$$$.

For smaller $$$k$$$ you can actually solve it in $$$\mathcal{O}(k \log k)$$$. You need to find $$$\dfrac{(1-x)(1-x^2) \cdots (1-x^n)}{(1-x)^n}$$$. The numerator can be found by finding it's $$$ln$$$ (in $$$\mathcal{O}(k \log n)$$$, since $$$ln(1-x^n)$$$ has only $$$k/n$$$ non-zero coefficients before $$$k$$$) and finding it's exponent, then we'll only need to divide it by the denominator, so for $$$k > n$$$ it's $$$\mathcal{O}(k \log k)$$$. I doudt it can be done faster than $$$\mathcal{O}(k)$$$, so I think it's pretty close to optimal.

maybe this will help(dp O(n^3)): https://cses.fi/problemset/result/8023530/

Hey, can you please share the problem and solution again, this link is not working.

@ravenr

Bit late, but here it is: https://ideone.com/kLkpPi, prob https://cses.fi/problemset/task/2229/

Imagine a permutation of elements $$$1,2,\ldots,n-1$$$ with $$$k'$$$ desired pairs then inserting $$$n$$$ in the position $$$k-k'$$$. This will make it a permutation of $$$1,2,\ldots,n$$$ with exactly $$$k$$$ desired pairs. (only possible if $$$0 \leq k-k' \leq n$$$ or in other words, $$$k-n \leq k' \leq k$$$)

You can count with DP in $$$O(nk)$$$, which is technically $$$O(n^{3})$$$ since $$$k \leq n^{2}$$$.

Pseudocode: