Description：

一个长度为 $n​$ 的序列 $A​$ 。如果 $A​$ 不是非降的，必须删去一个数，直到 $A​$ 非降为止。求有多少种不同的操作方案。

$1\leqslant n\leqslant 2000$

Solution：

首先一个比较好想的思路是设 $f[i][j]$ 表示前 $i$ 个数以 $i$ 结尾长度为 $j$ 的序列的个数，这个可以很容易的用树状数组优化成 $O(n^2\log n)$ ，那么他们乘上选择其他数的方案数（阶乘）加起来就是答案： $$ ans=\sum_{i=1}^n\sum_{j=1}^if[i][j]\times (n-j)! $$ 但是会发现这样会多算一些东西，也就是说有一些方案在还没有删完的时候就因为非降而被迫截止了，那么我们就要把它减掉，设 $g[i]$ 表示最终剩了长度为 $i$ 的方案数，那么计算方法为： $$ g[k]=\sum_{i=1}^nf[i][k]\times(n-k)!-\sum_{i=k+1}^ng[i]\times C^i_k\times(k-i)! $$ 因为每个长为 $i$ 的都会包含 $C^i_k$ 种长度为 $k$ 的，被选掉的方案数为 $n-k,n-k-1,\dots,k-i+1$ ，所以还要乘阶乘。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 1000000007

int n;

#define MAXN 2010

int a[MAXN],b[MAXN];

int f[MAXN][MAXN];

int g[MAXN];

int fac[MAXN],inv[MAXN];

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int C(int n,int m)

{

	return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

struct BIT

{

	int lowbit(int x){return x & (-x);}

	int c[MAXN];

	void add(int p,int x)

	{

		for(int i = p;i <= n;i += lowbit(i))

		{

			c[i] = ((c[i] + x) % MOD + MOD) % MOD;

		}

		return;

	}

	int query(int p)

	{

		int res = 0;

		for(int i = p;i >= 1;i -= lowbit(i))

		{

			res = ((res + c[i]) % MOD + MOD) % MOD;

		}

		return res;

	}

}s[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)b[i] = a[i];

	sort(b + 1,b + 1 + n);

	for(int i = 1;i <= n;++i)a[i] = lower_bound(b + 1,b + 1 + n,a[i]) - b;

	fac[0] = 1;

	for(int i = 1;i <= n;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	inv[n] = power(fac[n],MOD - 2);

	for(int i = n - 1;i >= 1;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

	for(int i = 1;i <= n;++i)

	{

		f[i][1] = 1;

		for(int j = i;j >= 1;--j)

		{

			f[i][j] = (f[i][j] + s[j - 1].query(a[i])) % MOD;

			s[j].add(a[i],f[i][j]);

		}

	}

	for(int k = n;k >= 1;--k)

	{

		for(int i = 1;i <= n;++i)

		{

			g[k] = (g[k] + f[i][k]) % MOD;

		}

		g[k] = 1ll * g[k] * fac[n - k] % MOD;

		for(int i = k + 1;i <= n;++i)

		{

			g[k] = (g[k] - 1ll * g[i] * C(i,k) % MOD * fac[i - k] % MOD + MOD) % MOD;

		}

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)ans = (ans + g[i]) % MOD;

	cout << ans << endl;

	return 0;

}