mydcwfy's Blog

Luogu P3600 随机数生成器

Posted on
Symbols count in article: 2.3k Reading time ≈ 5 mins.

一个 min-max 容斥题目。

题意：给定 $m$ 个区间 $[l_i, r_i]$，每次得到的权值为所有区间最小值的最大值，该序列 $n$ 个数均在 $[1, x]$ 内均匀随机，求期望权值的大小。$n, m, x\leq 2000$。

最小值的最大值显然不可做，考虑 min-max 容斥，将其转化为最小值的最小值。

那么式子可以写成：

注意到后面的式子仅与区间的并的长度有关，考虑将区间并的长度压进状态 DP 计算。

首先有一些区间是没有意义的，就是包含其他区间的区间，可以先排除掉。这样保证了所有区间按 $r$ 排序后 $l$ 也是递增的。

考虑 DP，设 $f(i, j)$ 表示最后一个位置是 $i$，且当前区间并的长度为 $j$ 的方案数。注意我们需要把 $(-1) ^ {|S| - 1}$ 的系数也带上。

考虑加入一个区间，那么我们需要计算的就是 $f(r_i, j)$，可以直接暴力计算：

这样计算时间复杂度为 $O(n ^ 2 m)$，无法通过，考虑使用前缀和优化。

前面一半很好前缀和，注意到后半部分他的 $t - j$ 一定的话，那么贡献到的位置也是一定的，因为区间并的变化量是 $r - t$。

那么，我们可以通过 $O(nm)$ 的时间计算 $f(i, j)$，前缀和一下即可得到区间并长度为 $j$ 的方案数（带系数）。

剩下的过程，我们发现 $x$ 很小，我们需要计算区间并长度为 $j$ 时最小值为 $x$ 的概率。考虑差分，计算最小值 $\leq x$ 的概率减去 $\leq x - 1$ 的概率即可。计算 $\leq x$ 的概率可以通过对立面（所有数都大于 $x$）来计算。后半部分时间复杂度 $O(nx)$。

于是我们在 $O(nm + nx)$ 的时间完成，可以通过。

注意求哪些区间没有覆盖其他区间的时候，相等的区间不能全部删去！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int main()
{
	std::cin >> n >> x >> m;
	for (int i = 1; i <= m; ++ i) scanf("%d %d", &a[i].l, &a[i].r);
	std::sort(a + 1, a + m + 1, [&](Interval &v1, Interval &v2) { return v1.r < v2.r; });
	int top = 0;
	for (int i = 1; i <= m; ++ i)
	{
		bool flag = true;
		for (int j = 1; j <= m && flag; ++ j)
			flag &= !(a[i].r >= a[j].r && a[i].l <= a[j].l) || (a[i].l == a[j].l && a[i].r == a[j].r);
		if (flag) tmp[++ top] = a[i];
	}
	std::swap(a, tmp), m = top;

	for (int i = 1; i <= m; ++ i) g[a[i].r].push_back(i);
	f[0][0] = pre1[0][0] = pre2[0][0] = Mod - 1;
	for (int r = 1; r <= n; ++ r)
	{
		for (int id : g[r])
		{
			int l = a[id].l;
			for (int len = r - l + 1, ls = r - l + 1; len <= r; ++ len)
				f[r][len] = (f[r][len] - (LL) pre1[l - 1][len - ls] - (pre2[r - 1][r - len] - pre2[l - 1][r - len]) - f[r][len] + 4LL * Mod) % Mod;
		}
		for (int len = 0; len <= r; ++ len)
			adj(pre1[r][len] = pre1[r - 1][len] + f[r][len] - Mod),
			adj(pre2[r][r - len] = pre2[r - 1][r - len] + f[r][len] - Mod);
	}
	int res = 0;
	for (int val = 1; val <= x; ++ val)
	{
		int ak = qpow(x) * (LL) (x - val) % Mod, p = ak, &cur = pro[val];
		for (int j = 1; j <= n; ++ j, p = (LL) p * ak % Mod)
			cur = (cur + (LL) p * pre1[n][j]) % Mod;
		adj(cur = 1 - cur);
		// std::cout << val << ' ' << cur << '\n';
		adj(cur -= pro[val - 1]), res = (res + (LL) cur * val) % Mod;
		// std::cout << val << ' ' << cur << '\n';
		adj(cur += pro[val - 1] - Mod);
	}
	std::cout << res << '\n';
	return 0;
}