P10592 BZOJ4361 isn
当一个序列删成非降序列的话那操作就要停止，所以我们要求的是最后一步刚好删成非降序列的操作数，但是这样做太复杂了，我们先不考虑停止操作，让他一直删下去。
这时我们就要知道长度为 \(i\) 的非降序列的数量然后才能计算答案，我们有 \(f_{i,j}\) 为第 \(i\) 个数长度为 \(j\) 的非降序列的长度，我们可以用树状数组优化，比如我们要求以 \(3\) 结尾的长度为 \(2\) 的非降子序列的数量，我们就用树状数组查询小于 \(3\) 的长度 \(1\) 的非降子序列的数量，这样计算的时间复杂度为 \(O(n^2\log n)\)。
接下我我们要统计长度为 \(i\) 的非降序列的总数量，我们有：
\[g_i=\sum_{i=1}^{n}\sum_{j=i}^{n}f_{j,i} \]现在知道数量如何计算方案数，对于删成一个长度为 \(i\) 的非降序列的方案数为 \((n-i)!\)，即删除数的全排列。总的方案数为：
\[ans=\sum_{i=1}^n g_i\times (n-i)! \]接下来加上停止操作，我们要排除不合法的方案，当我们删除最后一个数使得非降序列长度为 \(i\)，我们是从 \(i+1\) 转移过来，但是如果 \(i+1\) 删掉最后一个数使得非降序列长度为 \(i+1\) 的话就会停止操作使得不会再向下传递使我们造成贡献，所以我们要容斥掉那一部分，总计算为：
\[ans=\sum_{i=1}^n g_i\times (n-i)!-g_{i+1}\times (n-i-1)!\times (i+1) \]乘 \(i+1\) 是因为我们有 \(i+1\) 个数可以作长度为 \(i\) 的非降序列的最后一个删的数。
#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define re register
#define pir pair<int,int>
const int inf=1e9;
const int N=2e5+10;
const int mod=1e9+7;
using namespace std;
int n;
int a[N];
int b[N];
int f[3005][3005];
int t[3005][3005];
int fac[2005];
int g[N];
int lb(int x){
return x&-x;
}
void change(int x,int k,int z){
x++;
while(x<=2000){
(t[x][z]+=k)%=mod;
x+=lb(x);
}
}
int query(int x,int k){
x++;
int ans=0;
while(x){
ans+=t[x][k];
x-=lb(x);
ans%=mod;
}
return ans;
}
void init(){
fac[0]=1;
for(int i=1;i<=2000;i++){
fac[i]=fac[i-1]*i;
fac[i]%=mod;
}
sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b-1;
for(re int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+len+1,a[i])-b;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(re int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
init();
change(0,1,0);
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j;j--){
f[i][j]=query(a[i],j-1);
change(a[i],f[i][j],j);
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
(g[i]+=f[j][i])%=mod;
}
}
for(int i=1;i<=n;i++){
int x=g[i]*fac[n-i]%mod;
int y=g[i+1]*fac[n-i-1]%mod*(i+1)%mod;
if(i==n){
y=0;
}
ans=(ans+x-y+mod)%mod;
}
cout<<ans;
return 0;
}