先用树状数组求出g[i]表示长度为i的不降子序列个数。$O(n^2\log n)$

容斥，最终序列长度为i的方案数为g[i]*(n-i)!，但这里多计算了在删得只剩i个数之前就已经构成不降子序列的情况。

这时考虑最后是从哪个不降子序列删掉一个数的，g[i+1]*(n-i-1)!*(i+1)，这里显然不会重复斥掉方案。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 typedef long long ll; 6 using namespace std; 7  8 const int N=2010,mod=1e9+7; 9 int n,ans,a[N],b[N],fac[N],c[N][N],f[N][N],g[N];10 void add(int c[],int x,int k){ for (; x<=n; x+=x&-x) c[x]=(c[x]+k)%mod; }11 int que(int c[],int x){ int res=0; for (; x; x-=x&-x) res=(res+c[x])%mod; return res; }12 13 int main(){14     freopen("bzoj4361.in","r",stdin);15     freopen("bzoj4361.out","w",stdout);16     scanf("%d",&n);17     rep(i,1,n) scanf("%d",&a[i]),b[i]=a[i];18     sort(b+1,b+n+1);19     rep(i,1,n) a[i]=lower_bound(b+1,b+n+1,a[i])-b;20     fac[1]=1; rep(i,2,n) fac[i]=1ll*fac[i-1]*i%mod;21     add(c[0],1,1);22     rep(i,1,n) for (int j=i; j; j--)23         f[i][j]=(f[i][j]+que(c[j-1],a[i]))%mod,add(c[j],a[i],f[i][j]);24     rep(i,1,n) rep(j,i,n) g[i]=(g[i]+f[j][i])%mod;25     rep(i,1,n) ans=(ans+((1ll*fac[n-i]*g[i]%mod-1ll*fac[n-i-1]*g[i+1]%mod*(i+1)%mod)%mod+mod)%mod)%mod;26     printf("%d\n",ans);27     return 0;28 }