考虑从小到大加入一个数，
加入 i 时会增加大于0小于 i 对逆序对
那么就相当于求 ∑ai=k 的方案数，其中 ai<i
这就是个很经典的背包了——BZOJ2431
但是这题不能用背包来做
考虑容斥。
朴素的容斥要枚举哪些超过限制，这样复杂度是指数级别的，但是很多是有重复的
令 fi,j 表示用 i 个数组成 j 的方案数
gi=∑fi,j×(n+k−j−1n−1)
答案就是 ∑(−1)igi
fi,j 可以用旋转体积背包搞
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int N=200010,P=1e9+7; int n,k,S; ll f[510][N],inv[N],fac[N],a[N]; inline ll C(int x,int y){ return fac[x]*inv[y]%P*inv[x-y]%P; } int main(){ cin>>n>>k; S=sqrt(k<<1)+3; f[0][0]=1; for(int i=1;i<=S;i++) for(int j=i;j<=k;j++){ f[i][j]=(f[i][j-i]+f[i-1][j-i])%P; if(j>n) (f[i][j]-=f[i-1][j-n-1])%=P; } fac[0]=inv[0]=inv[1]=1; for(int i=1;i<=k+n;i++) fac[i]=fac[i-1]*i%P; for(int i=2;i<=k+n;i++) inv[i]=1LL*(P-P/i)*inv[P%i]%P; for(int i=1;i<=k+n;i++) (inv[i]*=inv[i-1])%=P; ll ans=C(n+k-1,n-1); for(int i=1;i<=S && i<=n;i++){ ll cur=0; for(int j=1;j<=k;j++) (cur+=f[i][j]*C(n+k-j-1,n-1))%=P; if(i&1) cur=-cur; (ans+=cur)%=P; } cout<<((ans+P)%P)<<endl; return 0; }