P3600 随机数生成器

题目描述

sol 研发了一个神奇的随机数系统，可以自动按照环境噪音生成真·随机数。

现在 sol 打算生成 $n$ 个 $[1, x]$ 的整数 $a_{1}, . . ., a_{n}$ ，然后进行一些询问。

$q$ 次询问，每次询问 $i$ 有两个参数 $l_{i}$ 和 $r_{i}$ ，sol 会计算 $min_{l_{i} \leq j \leq r_{i}} a_{j}$ （ $a$ 数组中下标在 $l_{i}, r_{i}$ 之间的数的最小值）。

最后测试结果会是这些询问得到的结果的最大值。

sol 进行了很多次实验，现在他想问问你测试结果的期望大小是多少，对 $666623333$ 取模。

第一行三个数 $n, x, q$ 。

下面 $q$ 行，第 $i$ 行两个数表示 $l_{i}$ 和 $r_{i}$ 。

一行一个数，表示答案。

1 2	`2 2 1 1 2`

1	`499967501`

1	`88571635`

提示：一个分数 $\frac{a}{b}$ 对 $666623333$ 取模的结果为 $a \times b^{666623331}$ 。

对于 $10 %$ 的数据， $n, x, q \leq 6$ 。

对于另外 $20 %$ 的数据， $q = 1$ 。

对于 $50 %$ 的数据， $n, x, q \leq 300$ 。

对于 $70 %$ 的数据， $n, x, q \leq 800$ 。

对于 $100 %$ 的数据， $1 \leq n, x, q \leq 2000$ ，对于每个 $i$ ， $1 \leq l_{i} \leq r_{i} \leq n$ 。

可以考虑对于每个 $i$ ，求出最后的最大值为 $i$ 的概率 $p_{i}$ ，然后答案就是： $\sum_{i = 1}^{x} i \times p_{i}$ 。

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

所以考虑差分：设 $P_{i}$ 表示最后的最大值 $\leq i$ 的概率，这样答案就是： $\sum_{i = 1}^{x} i \times (P_{i} - P_{i - 1})$ ，于是问题转化为求 $P_{i}$ 。

发现这个 $P_{i}$ 其实是一个计数问题（因为方案数除以 $x^{n}$ 就是概率），于是问题转化为“求所有区间的最小值的最大值 $\leq i$ 的方案数”。

设 $h (i)$ 表示最后的最大值 $\leq i$ 的方案数。等价于每个区间的最小值都 $\leq i$ ，也即每个区间内都存在一个 $\leq i$ 的数。

枚举 $j$ 表示有多少个数 $\leq i$ ，那么

h (i) = \sum_{j = 1}^{n} g (j) \times i^{j} \times (x - i)^{n - j}

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

下面我们开始求 $g (i)$ 。

定义状态： $f (i, j)$ 表示前 $i$ 个位置放了 $j$ 个点且第 $i$ 个位置必须放点，保证所有左端点 $\leq i$ 的区间至少有一个点的方案数。

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

转移：

f (i, j) = \sum_{f r_{k} + 1 \geq f l_{i}} f (k, j - 1)

发现可以参与转移的 $k$ 是一个连续的区间。使用前缀和优化可以降低复杂度至 $O (n^{2})$ 。

于是 $g (j)$ 就很容易算出：

g (j) = \sum_{f r_{i} = q} f (i, j)

总复杂度 $O (n^{2})$ 。