题目描述
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
输入 #1
1 | |
输出 #1
1 | |
输入输出样例 #2
输入 #2
1 | |
输出 #2
1 | |
说明/提示
提示：一个分数 $\frac{a}{b}$ 对 $666623333$ 取模的结果为 $a\times b^{666623331}~\mod~666623333$。
对于 $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$ 表示最后的最大值 $\le i$ 的概率，这样答案就是：$\sum_{i=1}^{x} i \times (P_i - P_{i-1})$，于是问题转化为求 $P_i$。
发现这个 $P_i$ 其实是一个计数问题（因为方案数除以 $x^n$ 就是概率），于是问题转化为“求所有区间的最小值的最大值 $\le i$ 的方案数”。
区间预处理
- 如果一个大区间包含了其他的小区间，那么这个大区间对最后的最大值是没有影响的，可以删掉；
- 对于剩下的没有包含关系的区间，按照左端点排序，那么右端点是严格单调递增的。
计数 DP
设 $h(i)$ 表示最后的最大值 $\le i$ 的方案数。等价于每个区间的最小值都 $\le i$，也即每个区间内都存在一个 $\le i$ 的数。
枚举 $j$ 表示有多少个数 $\le 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$ 个位置必须放点，保证所有左端点 $\le i$ 的区间至少有一个点的方案数。
预处理 $fl_i$ 和 $fr_i$ 表示覆盖位置 $i$ 的最左区间编号和最右区间编号。特殊地，如果 $i$ 不被任何区间包含，则 $fr_i$ 为右端点严格小于 $i$ 的最后一个区间，$fl_i = fr_i + 1$。
转移：
$$ f(i,j) = \sum_{fr_k+1 \ge fl_i} f(k, j-1) $$
发现可以参与转移的 $k$ 是一个连续的区间。使用前缀和优化可以降低复杂度至 $O(n^2)$。
于是 $g(j)$ 就很容易算出： $$ g(j) = \sum_{fr_i=q} f(i,j) $$ 总复杂度 $O(n^2)$。
