Problem

Count permutations of length $N$ with exactly $M$ inversions.

Solution

step 0

There is an easy $O(N^2)$ DP: let $dp_{i,j}$ be the number of ways for the first $i$ elements to have $j$ inversions. In the transition only the contribution of the $i$-th element matters:

\[dp_{i,j}=\sum_{k=j-i+1}^{j} {dp_{i-1,k}}\]

step 1

Look at what this $O(N^2 \times M)$ recurrence is doing. Each step chooses, for the $i$-th number, a contribution $k$ out of $[i,0)$.

So the problem becomes: count the solutions of $(\sum_{i=1}^{n} {x_i})=m$ with $x_i \in [0,i)$.

step 2

Since $x_i \in [0,i)$ is awkward, first allow $x_i \in [0,+\infty)$ and then subtract the invalid cases — those where some $A={x_i \mid x_i \ge i} \subset S=[1,n]$. By inclusion–exclusion,

\[\text{ans}=\sum_{A \in S} {(-1)^{|A|}\times f(A)}\]

where $f(A)$ is the number of solutions contributed by the set $A$.

To get $f(A)$:

Subproblem

Count the solutions of $(\sum_{i=1}^{n} {x_i})=m$ with $x_i \in [0,+\infty)$.

Stars and bars: split $m$ into $m$ ones and insert $n-1$ bars (bars may share a gap), so

\[\text{ans}=C_{m+n-1}^{n-1}\]
Back to the problem

Count the solutions of $(\sum_{i=1}^{n} {x_i})=m$ with $x_i \in [lim_i,+\infty)$.

Subtract $lim_i$ from every $x_i$; this reduces to the subproblem with $m$ replaced by $m-\sum_{i=1}^{n} {lim_i}$, so

\[\text{ans}=C_{m-(\sum{lim_i})+n-1}^{n-1}\]

Hence

\[f(A)=C_{m-(\sum{A_i})+n-1}^{n-1}\]

and therefore

\[\text{ans}=\sum_{A \in S} {(-1)^{|A|}\times C_{m-(\sum{A_i})+n-1}^{n-1}}\]

step 3

For the optimization, note that the contribution of $A$ depends only on $|A|$ and $\sum{A_i}$. Define $dp_{i,j}$ as the number of sets $A$ with $|A|=i$ and $\sum{A_i}=j$. Then

\[\text{ans}=\sum_{i=0}^{n} {\sum_{j=i\times(i+1)/2}^{m} {((-1)^{i}\times C_{m-j+n-1}^{n-1}}\times dp_{i,j})}\]

Since $j \in [i\times(i+1)/2,m]$, only $O(\sqrt{m})$ values of $j$ occur on average, so the answer is accumulated in $O(n\sqrt{m})$.

step 4

To compute $dp_{i,j}$: the set is unordered, so fix the elements of $A$ sorted in decreasing order into an array $a$ and DP over $a$. Split the new $a_i$ into the cases $=1$ and $\ne 1$:

\[dp_{i,j}=dp_{i-1,j-i}+dp_{i,j-i}\]

Also $a_i \le n$, so the cases exceeding $n$ must be subtracted; at most one $n+1$ can occur, so subtract exactly that case:

\[dp_{i,j}=dp_{i-1,j-i}+dp_{i,j-i}-dp_{i-1,j-n-1}\]

Time $O(n\sqrt{m})$.

step 5

Because of the memory limit, use a rolling array and accumulate the answer while running the DP.

Total time $O(n+m+n\sqrt{m})$, space $O(n+m)$.