自动搬运

查看原文

来自洛谷，原作者为

	Leasier 我们所知的是沧海一粟，我们所不知的是汪洋大海。

搬运于2025-08-24 22:47:12，当前版本为作者最后更新于2023-04-08 15:59:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

下文设 $a$ 按 $p$ 升序排序后的 $q'$ 为 $q_0$。

1. 求解 $f(a)_{\max}$

首先给出结论：答案为 $q_0$ 的 LIS 长度再加上 $n$。

为了证明这一点，首先我们需要证明如下结论：

• 任何一个满足 $\exists 1 \leq i \leq n$，使得 $p'_i$ 和 $q'_i$ 均不能产生贡献的方案，一定可以调整为 $\forall 1 \leq i \leq n$，使得 $p'_i$ 或 $q'_i$ 至少一个产生贡献的方案，且改后不劣。

证明：这里我们考虑从前往后依次调整每一个不满足条件的项。对于不产生贡献的 $(p'_i, q'_i)$，找到离 $i$ 最近的 $0 \leq j < i - 1$，使得 $\displaystyle\max_{k = 1}^j p'_k < p'_i$ 或 $\displaystyle\max_{k = 1}^j q'_k < q'_i$。下面讨论满足前一条件的情况。

这里考虑把 $a'_i$ 插入到 $a'_j$ 后面去，考虑一下贡献的变化量：

• 对于 $p'$ 而言，原 $p'_i$ 会带来 $1$ 的新贡献。
• 对于 $q'$ 而言，$\displaystyle\max_{k = 1}^j q'_k < q'_i$ 时会带来 $1$ 的新贡献，否则 $\displaystyle\max_{k = 1}^j q'_k < q'_i, \displaystyle\max_{k = 1}^{j + 1} q'_k > q'_i$，于是有 $q'_{j + 1} > q'_i$，即不会变劣。

则单次调整带来的新贡献 $\in [1, 2]$，满足不劣的条件。

于是，我们可以将任意方案调整为一个不劣且每对 $p'_i, q'_i$ 至少有一个产生贡献的情况。

现在我们只需要考虑两个均产生贡献的情况，则：

• 这些项的个数不超过 $q_0$ 的 LIS 长度，否则一定存在更长的 LIS。
• 抓出任意一个 $q_0$ 的 LIS 中的项都产生 $2$ 的贡献的 $a'$，我们可以用上面的方式将其调整至上限。

利用该结论，又因为本题中 $n$ 范围较小，直接暴力 dp 求 LIS 即可。时间复杂度为 $O(n^2)$。

2. 求解 $f(a)_{\max}$ 的方案数

考虑利用一定存在一个 $q_0$ 的 LIS，使得其顺序地作为每个最优 $a'$ 的子序列的性质 dp。

设 $g_i$ 表示 $q_0$ 的前缀 $[1, i]$ 的满足最后一个元素为 $i$ 的 LIS 长度。特别地，我们钦定 $g_{n + 1} = \displaystyle\max_{i = 1}^n g_i + 1$。

设 $dp_{i}$ 表示从后往前考虑到了 $[i, n + 1]$ 这个后缀，$i$ 在我们钦定的某个 LIS 中的方案数。

初值：$dp_{n + 1} = 1$。

转移：$dp_i = \displaystyle\sum_{j > i, (q_0)_j > (q_0)_i, g_j = g_i + 1}^{n + 1} dp_j C_{x + y}^x$，其中 $x$ 表示满足 $1 \leq k < i$ 且 $(q_0)_i < (q_0)_k < (q_0)_j$ 的 $k$ 的个数，$y$ 表示满足 $i < k < j$ 且 $(q_0)_k < (q_0)_i$ 的 $k$ 的个数。

• 解释一下这个转移：我们每次将满足第一个条件的元素 $k$ 顺序地放入 $a'$ 中的原 $a_i, a_j$ 之间，再将满足第二个条件的元素插板到其间。

答案：$dp_0$。

暴力实现是 $O(n^3)$ 的，直接上前缀和优化即可做到 $O(n^2)$。

综上，时间复杂度为 $O(n^2)$。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int mod = 998244353;
int dp1[10007], sum[10007][10007];
ll fac[10007], inv_fac[10007], dp2[10007];
pair<int, int> pr[10007];

inline ll quick_pow(ll x, ll p, ll mod){
	ll ans = 1;
	while (p){
		if (p & 1) ans = ans * x % mod;
		x = x * x % mod;
		p >>= 1;
	}
	return ans;
}

inline void init(int n){
	fac[0] = 1;
	for (int i = 1; i <= n; i++){
		fac[i] = fac[i - 1] * i % mod;
	}
	inv_fac[n] = quick_pow(fac[n], mod - 2, mod);
	for (int i = n - 1; i >= 0; i--){
		inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;
	}
}

inline int get_sum(int l1, int r1, int l2, int r2){
	return sum[r1][r2] - sum[l1 - 1][r2] - sum[r1][l2 - 1] + sum[l1 - 1][l2 - 1];
}

inline ll comb(int n, int m){
	if (n < 0 || m < 0 || n < m) return 0;
	return fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod;
}

int main(){
	int n, ni;
	cin >> n;
	ni = n + 1;
	init(n);
	for (int i = 1; i <= n; i++){
		cin >> pr[i].first;
	}
	for (int i = 1; i <= n; i++){
		cin >> pr[i].second;
	}
	sort(pr + 1, pr + n + 1);
	pr[ni].second = ni;
	for (int i = 1; i <= ni; i++){
		for (int j = 1; j < i; j++){
			if (pr[i].second > pr[j].second) dp1[i] = max(dp1[i], dp1[j]);
		}
		dp1[i]++;
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
			if (pr[i].second == j) sum[i][j]++;
		}
	}
	dp2[ni] = 1;
	for (int i = n; i >= 0; i--){
		for (int j = i + 1; j <= ni; j++){
			if (pr[j].second > pr[i].second && dp1[j] == dp1[i] + 1){
				int t = i == 0 ? 0 : get_sum(1, i - 1, pr[i].second + 1, pr[j].second - 1);
				dp2[i] = (dp2[i] + dp2[j] * comb(t + get_sum(i + 1, j - 1, 1, pr[i].second), t) % mod) % mod;
			}
		}
	}
	cout << dp1[ni] + n - 1 << " " << dp2[0];
	return 0;
}