自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:50:36，当前版本为作者最后更新于2018-10-23 17:56:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

讲一种不用期望 DP 的做法。

可以考虑对于每个 $i$ ，求出最后的最大值为 $i$ 的概率 $p_i$ ，然后答案就是：

众所周知，「最大值恰好为 $i$ 」往往是不好处理的。

所以考虑差分：设 $P_i$ 表示最后的最大值 $\le i$ 的概率，这样答案就是：

现在的问题就是如何求 $P_i$ 。

首先我们知道，如果一个区间包含了其他的区间，那么这个区间对最后的最大值是没有影响的。可以删掉。

这样如果把所有的区间按照左端点排序，那么右端点是严格单调递增的。

发现这个 $P_i$ 其实是一个计数问题（因为方案数除以 $x^n$ 就是概率），设 $h[i]$ 表示最后的最大值 $\le i$ 的方案数。

这等价于每个区间的最小值都 $\le i$ ，也就相当于每个区间内都存在一个 $\le i$ 的数。

我们不妨枚举 $j$ 表示有多少个数 $\le i$ ，那么 $h[i]$ 就等于：

其中 $g[j]$ 表示在 $[1,n]$ 内选出 $j$ 个点，使得每个区间至少包含一个点的方案数。

现在可以开始 DP 辣！

定义状态： $f[i][j]$ 表示前 $i$ 个位置放了 $j$ 个点且第 $i$ 个位置必须放点，覆盖所有左端点 $\le i$ 的区间的方案数。

预处理 $fl[i]$ 和 $fr[i]$ 表示覆盖位置 $i$ 的最左区间编号和最右区间编号。特殊地，如果 $i$ 不被任何区间包含，则 $fr[i]$ 为右端点严格小于 $i$ 的最后一个区间， $fl[i]=fr[i]+1$ 。

转移：

发现可以参与转移的 $k$ 是一个区间。前缀和优化， $O(n^2)$ 。

$g[j]$ 就很容易算出：

复杂度 $O(n^2)$ 。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
using namespace std;

inline int read()
{
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

template <class T>
T Min(T a, T b) {return a < b ? a : b;}

template <class T>
T Max(T a, T b) {return a > b ? a : b;}

const int N = 2005, ZZQ = 666623333, INF = 0x3f3f3f3f;
int n, m, X, q, fl[N], fr[N], f[N][N], sum[N][N], g[N], h[N], divis, ans;

struct node
{
	int l, r;
} a[N], b[N];

bool comp(node a, node b)
{
	return a.l < b.l || (a.l == b.l && a.r < b.r);
}

int qpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1) res = 1ll * res * a % ZZQ;
		a = 1ll * a * a % ZZQ;
		b >>= 1;
	}
	return res;
}

int main()
{
	int i, j, top = 0;
	n = read(); X = read(); q = read();
	For (i, 1, n) fl[i] = INF, fr[i] = -INF;
	For (i, 1, q) b[i].l = read(), b[i].r = read();
	sort(b + 1, b + q + 1, comp);
	For (i, 1, q)
	{
		if (i > 1 && b[i].l == b[i - 1].l) continue;
		while (top && a[top].r >= b[i].r) top--;
		a[++top] = b[i];
	}
	q = top;
	For (i, 1, q) For (j, a[i].l, a[i].r)
		fl[j] = Min(fl[j], i), fr[j] = Max(fr[j], i);
	top = 0;
	For (i, 1, n)
		if (fl[i] == INF) fl[i] = top + 1, fr[i] = top;
		else top = Max(top, fr[i]);
	f[0][0] = sum[0][0] = 1;
	top = 0;
	For (i, 1, n)
	{
		while (top < i - 1 && fr[top] + 1 < fl[i]) top++;
		For (j, 1, i) f[i][j] = (sum[i - 1][j - 1] - (top ?
			sum[top - 1][j - 1] : 0) + ZZQ) % ZZQ;
		For (j, 0, i) sum[i][j] = (sum[i - 1][j] + f[i][j]) % ZZQ;
	}
	For (i, 1, n) if (fr[i] == q) For (j, 1, n)
		g[j] = (g[j] + f[i][j]) % ZZQ;
	For (i, 1, X) For (j, 1, n)
		h[i] = (h[i] + 1ll * qpow(i, j) * qpow(X - i, n - j) % ZZQ
			* g[j] % ZZQ) % ZZQ;
	Rof (i, X, 1) h[i] = (h[i] - h[i - 1] + ZZQ) % ZZQ;
	divis = qpow(qpow(X, n), ZZQ - 2);
	For (i, 1, X) ans = (ans + 1ll * i * h[i] % ZZQ * divis % ZZQ) % ZZQ;
	cout << ans << endl;
	return 0;
}