对于这个 \(\max\) 似乎没有什么好的办法，考虑 \(\min-\max\) 反演。
记 \(t_i\) 为第 \(i\) 格被染黑的时间，有 \(E(\max(t_i)) = \sum\limits_{S} (-1)^{|S| + 1} E(\min(t_i))(i\in S)\)。
考虑如果知道了 \(S\)，那么就可以知道 \(c = \sum\limits_{i = 1}^m [[l_j, r_j]\cap S\not= \varnothing]\)。
\(x\) 意义是只要选到了这 \(x\) 条中的任意一条就能成为 \(\min\)，概率为 \(\frac{c}{m}\)，那么 \(E(\min) = \frac{m}{c}\)。
但是因为 \(n\) 的范围肯定不能直接枚举 \(S\)。
考虑到实际上只需要知道 \(c\) 和 \(|S|\) 还有对应的方案数就可以得到答案，前者是为了算期望，而后者是系数。
于是初步想法是把 \(c, |S|\) 扔进状态，维护方案数，同时为了转移还需要再添加一维表示处理到的前缀。
即设 \(f_{i, c, |S|}\) 为处理到 \([1, i]\) 且 \(i\) 必选同时 \(c, |S|\) 是这些值对应的方案数，转移可以考虑从前面的一个端点转移过来。
考虑到转移肯定就是多了 \(i\) 这个点，\(|S|\) 带来的影响就是 \(+1\)，对贡献的影响就是 \(\times (-1)\)。
那么就可以想到把 \((-1)^{|S| + 1}\) 这个东西也放到维护的值里面去。
记上面设的 \(\text{DP}\) 是 \(g\)，即设 \(f_{i, c}\) 为处理到 \([1, i]\) 且 \(i\) 必选同时 \(c\) 是这个值时 \(\sum\limits_{j = 0}^m (-1)^{j + 1} g_{i, c, j}\) 的值。
为避免算重线段，可以预处理对于 \(x, y\) 满足 \(x < l, l\le y\le r\) 的线段条数 \(v_{x, y}\)。
转移即为 \(f_{i, c} = \sum\limits_{k = 0}^{i - 1} f_{k, c - v_{k, i}}\times (-1)\)。
时间复杂度 \(O(n^2m)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
const i64 mod = 998244353;
const int maxn = 4e2 + 10;
i64 c[maxn][maxn], f[maxn][maxn];
i64 inv[maxn];
int main() {
int n, m; scanf("%d%d", &n, &m);
inv[0] = inv[1] = 1;
for (int i = 2; i <= m; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for (int i = 1, l, r; i <= m; i++) {
scanf("%d%d", &l, &r);
for (int x = 0; x < l; x++) for (int y = l; y <= r; y++) c[x][y]++;
}
f[0][0] = mod - 1;
for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++)
for (int k = 0; k < i; k++) if (j >= c[k][i])
(f[i][j] += mod - f[k][j - c[k][i]]) %= mod;
i64 ans = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) (ans += f[i][j] * m % mod * inv[j] % mod) %= mod;
printf("%lld\n", ans);
return 0;
}