首先我们考虑一个暴力的dp：
我们从小到大加入每个数，当我们加入第$i$个数时，可能产生的逆序对数量是$[0,i-1]$（这个证明考虑把第$i$个数放在哪即可），这样可以列出一个递推式：
设状态$dp[i][j]$表示已经加到了第$i$个数，此时的逆序对个数为$j$，那么有转移：$dp[i][j]=sum_{k=j-i+1}^{j}dp[i-1][k]$
这个转移的时间复杂度是$O(n^{3})$
然后考虑优化，显然那个求和式可以用前缀和优化，时间复杂度降成$O(n^{2})$
这样已经可以通过bzoj上的题目了，但loj上的是加强版，过不去
考虑其他做法：
（如果您不喜欢多项式可以直接跳到解法2）
首先，考虑生成函数：对每个位置构造一个生成函数，那么最后的结论就是：
$F(x)=prod_{i=0}^{n-1}(sum_{j=0}^{i}x^{j})$
整理一下后面，就是：
$F(x)=prod_{i=0}^{n-1}frac{1-x^{i+1}}{1-x}$
然后整体合并一下，就得到：
$F(x)=frac{prod_{i=1}^{n}(1-x^{i})}{(1-x)^{n}}$
有点奇怪，两边取下对数：
$lnF(x)=sum_{i=1}^{n}ln(1-x^{i})-nln(1-x)$
$ln(1-x^{i})$这个东西已经展开过很多次了...
对$ln(1-x^{i})$求导得到：
$frac{-ix^{i-1}}{1-x^{i}}$
把下半部分恢复成等比数列求和的形式：
$-ix^{i-1}sum_{j=0}^{∞}x^{ij}$
把外面的系数移进去：
$-sum_{j=0}^{∞}ix^{ij+(i-1)}$
然后积分：
$int -sum_{j=0}^{∞}ix^{ij+(i-1)}=-sum_{j=1}^{∞}frac{i}{ij+i}x^{ij+i}$
约分一下，就得到了：
$-sum_{j=0}^{∞}frac{1}{j+1}x^{ij+i}$
令$j=j+1$，有：
$-sum_{j=1}^{∞}frac{1}{j}x^{ij}$
对一个函数先求导再积分得到的就是原函数，因此有：
$ln(1-x^{i})=-sum_{j=1}^{∞}frac{1}{j}x^{ij}$
这样的话可以通过枚举倍数做到$O(nlnn)$（即调和级数）求出系数，然后多项式exp即可，注意这里由于模数不好，需要用到MTT，总时间复杂度仍为$O(nlog_{2}n)$
其实后面的部分基本与这道题一致，基本步骤也相同
但是...由于过于毒瘤，我并不想写一遍...
（更何况还多了一大堆东西）
因此我们考虑做法二
原来的dp已经被压榨到足够优秀，剩下的部分很困难了，因此我们考虑转化问题：
回到最开始的思想：
我们从小到大加入每个数，当我们加入第$i$个数时，可能产生的逆序对数量是$[0,i-1]$
那么，如果我们设$x_{i}$表示加入第$i$个数时产生的逆序对数量，我们实际只是在解这个不定方程：
$sum_{i=1}^{n}x_{i}=k$
其中对任意$iin [1,n]$，有$x_{i}in [0,i-1]$
我们实际是在求这个不定方程解的组数！
每个变量都有上界，这很不好求...
因此我们考虑容斥，容斥系数-1
还是要容斥的...
我们不妨假设有某个位置不合法，设这个位置为$p$，那么显然有表达式：
$x_{p}geq p-1$
那么我们考虑一个增量$delta_{p}=x_{p}-p+1$，那么我们在等式两侧同时去掉这个增量，新的变量记作$x_{p}^{'}$，转化后的方程即为：
$x_{1}+x_{2}+...+x_{p}^{'}+...+x_{n}=k-delta_{p}$
然而，在这种情况下，我们事实上仍然无法保证剩下的位置均合法，因此这样统计出的是有重复的！
据此，我们进一步分析：如果我们先统计出总的增量$delta$，然后将这个增量分配给几个单独的$delta_{p}$即可，然后用容斥原理计算就可以了
设状态$f[i][j]$表示用$i$个$[1,n]$之间的数求和，和为$j$的方案数，那么每一个总增量$delta$对答案的贡献即为$C_{n+k-delta-1}^{n-1}(sum_{i=0}^{sqrt{k}}(-1)^{i}f[i][delta])$
为什么上界是$sqrt{k}$？
考虑$m$个互不相同的数求和的最小值为$frac{m(m+1)}{2}$，由于$delta leq k$，因此有效的数字个数应当是$sqrt{k}$级别的
前面乘的组合数也就是剩下的那个不定方程的解的组数，后面是容斥方案数
这样的话我们只需计算出$f[i][j]$即可
考虑转移：由于我们要求数组中每个数都不同，所以可以把操作看成对数组中每个数加一，因此有转移：
$f[i][j]=f[i][j-i]+f[i-1][j-1]$
原理：如果元素个数不变，那么每个数加一之前的值即为$f[i][j-i]$
如果元素个数改变，那么一定是原数组中每个数加一之后再放下一个$1$，从$f[i-1][j-i]$转移过来
但是我们注意到，每个元素有一个上界就是$n$，但是这样直接算很有可能某个元素超过了$n$！
我们注意到每个元素+1的次数不能超过$n$，因此我们最后还需要去掉一个超过n的情况，也就是加上1之后某个数的大小超过$n$，变成了$n+1$！
最终的表达式即为$f[i][j]=f[i][j-i]+f[i-1][j-i]-f[i-1][j-n-1]$
这样这题就算做完了
当然其实还有方法三
生成函数结合容斥原理
考虑上面那个生成函数，发现我们要求的只是一个系数，因此我们考虑能不能直接搞出来
先考虑分母：
$frac{1}{(1-x)^{n}}=(sum_{i=0}^{infty}x^{i})^{n}=sum_{i=0}^{infty} C_{n+i-1}^{n-1}x^{i}$
再考虑分子：
$prod_{i=1}^{n}(1-x^{i})$
如果我们展开这个东西，那么$x^{i}$项前的系数即为用$j$个互不相同的$[1,n]$的数表示出$i$的方案数再乘一个$(-1)^{j}$
因此我们考虑直接计算这个东西
设状态$f[i][j]$表示用$i$个互不相同的数表示出和为$j$的方案数
然而由于选出的数不能重复，因此这个dp根本搞不了
考虑进一步转化问题：
如果我们给一个序呢？
我们设状态$f[i][j]$表示用$i$个互不相同的数表示出和为$j$的方案数，要求构造出序列{$a_{i}$}的是个上升序列
这样的话我们考虑对序列翻转后差分，设{$a_{i}$}是反转后的序列，令$b_{i}=a_{i}-a_{i+1}$，那么每个$b_{i}$对答案的贡献即为$ib_{i}$
这样的话我们只需构造出序列$b$即可
那么我们设状态$f[i][j]$表示已经放了$i$个$b$，总贡献为$j$的方案数，那么这个就有以下几个转移方向：
首先：个数不变，第$i$个$b$加一，那么他的贡献是$i$，因此$f[i][j]+=f[i][j-i]$
其次：个数改变，在位置$i$上放了个1，那么其共享仍为$i$，因此$f[i][j]+=f[i-1][j-i]$
但是，每个位置上的数都不应当超过$n$，但我们是逐次加1来增大的$b$序列，因此如果出现大于$n$的情况，那么一定是出现了$n+1$！
因此我们去掉这个$n+1$即可，转移即为$f[i][j]-=f[i-1][j-n-1]$
这样$f[i][j]$就搞出来了，可以发现这与最初的问题等价
这样我们最后卷积算出$k$位置的系数就好了
（可以看到方法二、三思想稍有区别，但殊途同归，代码其实是一样的qwq）
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #define ll long long using namespace std; const ll mode=1000000007; const int lim=450; ll inv[200005]; ll minv[200005]; ll mul[200005]; ll dp[455][100005]; ll n,k; void init() { inv[0]=inv[1]=mul[0]=mul[1]=minv[0]=minv[1]=1; for(int i=2;i<=200000;i++) { inv[i]=(mode-mode/i)*inv[mode%i]%mode; minv[i]=minv[i-1]*inv[i]%mode; mul[i]=mul[i-1]*i%mode; } } ll C(ll x,ll y) { if(x<y)return 0; return mul[x]*minv[y]%mode*minv[x-y]%mode; } int main() { init(); scanf("%lld%lld",&n,&k); dp[0][0]=1; for(int i=1;i<=lim;i++) { for(int j=0;j<=k;j++) { if(j>=i)dp[i][j]=(dp[i][j-i]+dp[i-1][j-i])%mode; if(j>=n+1)dp[i][j]=(dp[i][j]+mode-dp[i-1][j-n-1])%mode; } } ll ans=0; for(int i=0;i<=k;i++) { ll temps=0; ll f=1; for(int j=0;j<=lim;j++)temps=(temps+f*dp[j][i]+mode)%mode,f=-f; temps=temps*C(n+k-i-1,n-1)%mode; ans=(ans+temps)%mode; } printf("%lld ",ans); return 0; }