自动搬运

查看原文

来自洛谷，原作者为

	2huk Where should my destinaion be at? 我问我自己。

搬运于2025-08-24 22:59:28，当前版本为作者最后更新于2024-09-15 11:06:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

很好很好的算答案方式。

小 D 有一个长度为 $n$ 的序列。如果序列不是非降的，他会选择一个元素删去，直到序列变成非降的，这时停止操作。求操作序列种类数，对 $10^9+7$ 取模。

两个操作序列不同，当且仅当它们长度不同或者某一次操作删除的元素位置不同。

$n \le 2000,1 \le a_i \le 10^9$。

这个问题的难点在于，如果此时序列已经非降了那么此时必须停止。我们考虑如果没有这个限制的问题：

小 D 有一个长度为 $n$ 的序列。如果序列不是非降的，他会选择一个元素删去，直到序列变成非降的，这时可以选择停止操作，也可以不停止。求操作序列种类数，对 $10^9+7$ 取模。

我们考虑原序列的任意一个上升子序列对答案的影响，即有多少种将其它元素删除的方式，使得最终整个序列只剩这个子序列。

令这个上升子序列长度为 $i$。显然这个的答案是 $(n - i)!$，即其它元素可以任意选择顺序删除。

暴力枚举这个上升子序列仍然是指数复杂度。考虑 DP。

设 $f(i, j)$ 表示有多少上升子序列以 $i$ 结尾且长度为 $j$。转移显然：

$$f(i, j) = \left\{\begin{matrix}1 &, j=1 \\ \sum_{k=1}^{i-1}[a_k \le a_i]f(k,j-1) &,j \ne 1 \end{matrix}\right. $$

可以用树状数组轻易优化至 $\mathcal O(n^2 \log n)$。

考虑统计答案。令 $g(i) = \sum_{j=1}^i f(j, i)$，即有多少个上升子序列的长度为 $i$。那么答案为：

$$\sum_{i=1}^n g(i) \cdot (n - i)!$$

至此我们用 $\mathcal O(n^2 \log n)$ 的复杂度通过了弱化版。

我们考虑原问题比弱化版的答案少在了哪些地方。即考虑一个上升子序列什么时候产生的贡献变小。

对于一个长度为 $i$ 的上升子序列 $s$，如果存在 $j$ 个长度为 $i + 1$ 的上升子序列完全包含它，那么当小 D 通过若干次删除操作得到这 $j$ 个子序列后，游戏应当在此时停止。不难发现只有这种情况会导致 $s$ 不产生贡献。

所以答案比弱化版少了：

$$\begin{matrix} \sum_{s,j} j \times (n-(i+1))! \\ \tiny s\text{ is an increasing subsequence of length }i\text{ of }a.\\ \tiny {\text{There are }j\text{ increasing subsequences of length }i+1\text{ that completely contain }s.} \end{matrix} $$

暴力枚举 $s$ 还是指数复杂度。

显然每个 $s$ 对应的 $j$ 的和为 $g(i + 1) \cdot (i + 1)$。这是因为一个长度 $i + 1$ 的上升子序列中含有 $i + 1$ 个这样的 $s$。

所以答案为：

$$\sum_{i=1}^n\left[ g(i) \cdot (n-i)! - g(i+1)\cdot (i+1)\cdot(n-i-1)! \right] $$

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2024, P = 1e9 + 7;

int n, a[N], b[N];
int f[N][N];		// 以 i 结尾的长度为 j 的子序列数量
int g[N], nums;

struct Tree {
	int tr[N];
	
	void modify(int x, int d) {
		for (int i = x; i <= nums; i += i & -i)
			tr[i] = (tr[i] + d) % P;
	}
	
	int query(int x) {
		int res = 0;
		for (int i = x; i; i -= i & -i)
			res = (res + tr[i]) % P;
		return res;
	}
}T[N];

int fac[N];

signed main() {
	fac[0] = 1;
	for (int i = 1; i < N; ++ i ) fac[i] = 1ll * fac[i - 1] * i % P;
	
	cin >> n;
	
	for (int i = 1; i <= n; ++ i ) {
		cin >> a[i];
		b[i] = a[i];
	}
	
	sort(b + 1, b + n + 1);
	nums = unique(b + 1, b + n + 1) - b - 1;
	
	for (int i = 1; i <= n; ++ i ) {
		a[i] = lower_bound(b + 1, b + nums + 1, a[i]) - b;
	}
	
	for (int i = 1; i <= n; ++ i ) {
		f[i][1] = 1;
		for (int j = 2; j <= i; ++ j ) {
			f[i][j] = T[j - 1].query(a[i]);
		}
		
		for (int j = 1; j <= i; ++ j ) {
			T[j].modify(a[i], f[i][j]);
		}
	}
	
	for (int i = 1; i <= n; ++ i )
		for (int j = 1; j <= i; ++ j )
			g[j] = (g[j] + 1ll * fac[n - j] * f[i][j] % P) % P;
	
	int res = 0;
	for (int i = 1; i <= n; ++ i )
		res = ((res + g[i] - g[i + 1] * (i + 1) % P) % P + P) % P;
	cout << res;
	
	return 0;
}