这篇题解更像对他人题解的吐槽和补充？
考虑答案
$E[X] = \sum\limits_{i = 1}^{x} i P(X = i)$
$P(X = i)$不好求................（其实完全可以求的......而且求法和下面的方法蜜汁相似......）
那么，我们考虑整数概率公式（既然$P(X = i)$能求，那这公式到底有什么用？）
$E[X] = \sum\limits_{i = 1}^{x} P(x \geq i)$
当然，你也可以选择求$E[X] = \sum\limits_{i = 1}^{x} i * (P(x \geq i) - P(x \geq i + 1))$
或者求$E[X] = \sum\limits_{i = 1}^{x} i * (P(x \leq i + 1) - P(x \leq i))$
不过方法没什么本质的区别..........
那么，考虑求枚举$x$后求$P(x \geq i)$，由于题目是最大值，这是“或”概率，不好求
因此考虑“非与非”，即求反面$1 - P(x \leq i - 1)$
相信你能发现，被包含的区间的答案是无所谓的...
因此，将区间去包含就成了随着左端点递增，右端点递增的局面
接着，考虑一个点能让哪些区间得出正确的结果然后转移
不妨设一个点能影响的区间为$[L[i], R[i]]$，记为$S[i]$
令$f[i]$表示让第$i$个小于$x$，并且$1 ... R[i]$的所有询问都合法的概率
为了方便书写，令随机出小于等于$v$的数的概率为$p$，那么$p = \frac{v}{x}$
那么，我们枚举跟$i$的区间有交的$j$，然后让$[i + 1, j - 1]$强行大于$v$转移
（注意，需要认为存在一段$[0, 0]$的区间，并且$0$已经选择了小于等于$v$的数来辅助转移，因此开始要特判...）
$f[i] = （p * \sum\limits_{S[i] \cap S[j] \neq \varnothing} f[j] * (1 - p)^{i - j - 1}）$
用$two - pointer$和前缀和可以优化到$O(n)$
（只要去掉开头的$p$就是求$P(x = i)$了，但是这么做在有点没被区间覆盖时不能采用下面的算法）
（需要单独把没有被区间覆盖的点拿出来，不让他们参与转移...毕竟$p + 1 - p = 1$，但是$1 - p \neq 1$，这么写略麻烦）
那如果有些点完全没被区间覆盖怎么办呢？
不妨设$[l_1, r_1], [l_2, r_2]$编号为$i, j$，且有$l_1 \leq r_1 < l_2 \leq r_2$
那么对于$[r_1 + 1, l_2 - 1]$中的点，令其$S = [j, i]$（没写错）
这时，$i$能顺利地转移到$S$一次，同时把$S$和右边的第一块没有被两个区间交的部分绑在了一起转移....
（这可以保证增加区间$[0, 0]$和区间$[n + 1, n+1]$的正确性）
（然而出题人并没有谈，所以数据保证所有的点都被区间覆盖？）
最后求$P(x < i)$的时候，相当于还单独存在一段$[n + 1, n + 1]$的区间，并且$n + 1$已经选择了小于$i$的数...
可以选择加上这段区间或者最后特判下....
复杂度$O(nx)$
注：$luogu$最近是不是慢了....
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; extern inline char gc() {
static char RR[], *S = RR + , *T = RR + ;
if(S == T) fread(RR, , , stdin), S = RR;
return *S ++;
}
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
} #define ri register int
#define sid 2005
const int mod = ; int n, x, q, ans;
int ps[sid], snp;
int L[sid], R[sid], f[sid], inv[sid], fac[sid];
struct seg {
int l, r;
friend bool operator < (seg a, seg b)
{ return a.l < b.l || (a.l == b.l && a.r > b.r); }
} s[sid]; int fp(int a, int k) {
int ret = ;
for( ; k; k >>= , a = 1ll * a * a % mod)
if(k & ) ret = 1ll * ret * a % mod;
return ret;
} int main() {
n = read(); x = read(); q = read();
for(ri i = ; i <= q; i ++) {
int l = read(), r = read();
s[i].l = l; s[i]. r = r;
} sort(s + , s + q + );
for(ri i = ; i <= q; i ++) {
while(s[i].r <= s[ps[snp]].r) snp --;
ps[++ snp] = i;
}
q = snp; for(ri i = ; i <= q; i ++) s[i] = s[ps[i]]; int fr = , to = ;
for(ri i = ; i <= n; i ++) {
while(to < q && s[to + ].l <= i) to ++;
while(fr <= to && s[fr].r < i) fr ++;
L[i] = fr; R[i] = to;
} for(ri v = ; v <= x; v ++) {
int p = 1ll * (v - ) * fp(x, mod - ) % mod, bp = ( - p + mod) % mod;
int pc = fp(bp, mod - ), sum = ;
inv[] = fac[] = f[] = ;
for(ri i = ; i <= n; i ++) {
inv[i] = 1ll * inv[i - ] * pc % mod;
fac[i] = 1ll * fac[i - ] * bp % mod;
}
for(ri i = , j = ; i <= n; i ++) {
while(j < i && R[j] < L[i] - ) ((sum -= 1ll * f[j] * inv[j] % mod) += mod) %= mod, j ++;
f[i] = 1ll * sum * fac[i - ] % mod * p % mod;
(sum += 1ll * f[i] * inv[i] % mod) %= mod;
}
int anp = ;
for(ri i = ; i <= n; i ++)
if(R[i] == q) (anp += 1ll * f[i] * fac[n - i] % mod) %= mod;
(ans += ( - anp + mod) % mod) %= mod;
}
printf("%d\n", ans);
return ;
}