题意
求一个长度为$N$且恰好有$M$个逆序对的排列个数。
题解
step 0
容易有一个$O(N^2)$的$dp$：定义$dp_{i,j}$表示前$i$有$j$个逆序对。
转移时只需要关注这一个对前$i-1$做的贡献即可：$dp_{i,j}=\sum_{k=j-i+1}^{j} {dp_{i-1,k}}$
step 1
观察$O(N^2 \times M) \ dp$方程：$dp_{i,j}=\sum_{k=j-i+1}^{j} {dp_{i-1,k}}$
每一步本质上是在为第$i$个数从$[i,0)$中选一个贡献为$k$的值
所以原问题可以转化为：
有方程：$(\sum_{i=1}^{n} {x_i})=m$,$x_i \in [0,i)$,求其解的个数.
step 2
因为$x_i \in [0,i)$比较恶心，所以先考虑$x_i \in [0,+\infty)$的情况，再减去不合法的，即${x}$中有一些$A={x_i|x_i \ge i} \subset S=[1,n]$,于是使用容斥，有：
\[\text{ans}=\sum_{A \in S} {(-1)^{|A|}\times f(A)}\]$f(A)$为集合$A$的贡献（方案数）。
现在求$f(A)$:
子问题
有方程：$(\sum_{i=1}^{n} {x_i})=m$,$x_i \in [0,+ \infty)$,求其解的个数.
考虑使用插板法，即把$m$拆成$m$个$1$，再插$n-1$个板进去（注意可以插同一个空），所以有：
\[\text{ans}=C_{m+n-1}^{n-1}\]
原问题
有方程：$(\sum_{i=1}^{n} {x_i})=m$,$x_i \in [lim_i,+ \infty)$,求其解的个数.
可以先把每个$x_i$减去$lim_i$，就变成了子问题，只不过$m$变为了$m-\sum_{i=1}^{n} {lim_i}$，所以有：
\[\text{ans}=C_{m-(\sum{lim_i})+n-1}^{n-1}\]
所以有： \(f(A)=C_{m-(\sum{A_i})+n-1}^{n-1}\)
于是：
\[\text{ans}=\sum_{A \in S} {(-1)^{|A|}\times C_{m-(\sum{A_i})+n-1}^{n-1}}\]step 3
考虑优化，可以发现$A$的贡献只与|A|和$\sum{A_i}$有关，所以我们定义$dp_{i,j}$表示$|A|=i$且$\sum{A_i}=j$的$A$的数量，于是：
\[\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})}\]因为$j \in [i\times(i+1)/2,m]$，所以实际上平均下来$j$只有$O(\sqrt{m})$个，所以统计答案是$O(n\sqrt{m})$的。
step 4
考虑求$dp_{i,j}$，因为集合无序，所以我们钦定$A$中的元素降序排序后形成数组$a$,考虑对$a$进行$dp$，将新的$a_i$分成$=1$与$\ne 1$考虑，有：
\[dp_{i,j}=dp_{i-1,j-i}+dp_{i,j-i}\]又因有$a_i \le n$，所以要减去超过$n$的情况，这时只可能出现一个$n+1$的情况，所以再减去这种情况即可：
\[dp_{i,j}=dp_{i-1,j-i}+dp_{i,j-i}-dp_{i-1,j-n-1}\]时间复杂度$O(n\sqrt{m})$
step 5
由于卡空间，所以使用滚动数组优化，边$dp$边统计答案即可。
总时间复杂度$O(n+m+n\sqrt{m})$，空间复杂度$O(n+m)$。
