本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-05 11:26:30

:::::info[题目基本信息] 考察：容斥原理，动态规划 DP（$2835$）。
题目简述：
给定序列 $\{l_m\}$ 和 $\{r_m\}$，同时有一个序列 $\{c_n\}$，初始时 $\forall i\in[1,n],c_i=0$，求进行下面操作使得 $\forall i\in[1,n],c_i=1$ 的期望次数对 $998244353$ 取模的结果。

• 等概率选取一个整数 $i$ 满足 $i\in[1,m]$，然后 $\forall pos\in[l_i,r_i],c_{pos}\leftarrow 1$。

数据范围：

• $1\le n,m\le 400$
• $\forall i\in[1,m],1\le l_i\le r_i\le n$
• $\forall i\in[1,n],\exist j\in[1,m],l_j\le i\le r_j$ ::::: 设 $t_i$ 为 $c_i$ 第一次变成 $1$ 的已进行操作数，显然最后答案就是 $\displaystyle E\max_{i=1}^nt_i$，但是由于 $\displaystyle E\max_{i=1}^n t_i\ne\max_{i=1}^n Et_i$，所以我们不能直接拆，也不好直接算，我们就要考虑容斥。
  对于极值，我们有 Min-Max 容斥，对于本题式子为：
  $$\max_{x\in S}t_x=\sum_{T\subseteq S,T\ne\arnothing}(-1)^{|T|+1}\min_{x\in T}t_x$$ :::::success[证明] 考虑对于 $S$ 中的每个元素分别计算贡献：
  设 $\displaystyle p=\min_{x\in T\subseteq S}t_x$，此时，要是最小值等于 $p$，大于 $p$ 的可选可不选，小于它的一定不能选，贡献就是：
  $$\begin{aligned}\sum_{T\subseteq \{x|x\in S,x>p\},p\in T}(-1)^{|T|+1}p&=p\sum_{T\subseteq \{x|x\in S,x>p\}}(-1)^{|T|}\&=p\sum_{T'=0}^{\sum_{x\in S}[x>p]}\sum_{T\subseteq\{x|x\in S,x>p\},|T|=T'}(-1)^{T'}\&=p\sum_{T'=0}^{\sum_{x\in S}[x>p]}(-1)^{T'}\binom{\sum_{x\in S}[x>p]}{T'}\&=p\sum_{T'=0}^{\sum_{x\in S}[x>p]}(-1)^{T'}1^{\sum_{x\in S}[x>p]-T'}\binom{\sum_{x\in S}[x>p]}{T'}\&=p(-1+1)^{\sum_{x\in S}[x>p]}\&=[\sum_{x\in S}[x>p]=0]p\&=\max_{x\in S}t_x\end{aligned}$$ ::::: 显然上面的式子在期望意义下也成立，所以直接套用到本题。
  在本题中 $\displaystyle E\min_{x\in T\subseteq S}t_x$ 是好算的，表达的意思就是 $T$ 中有元素 $x$ 使得 $c_x=1$ 的已进行操作数的期望，若 $p$ 表示所有 $[l_i,r_i]$ 与 $T$ 有交的个数，即 $\displaystyle p=\sum_{i=1}^m[[l_i,r_i]\cap T\ne\arnothing]$，容易发现会有 $\dfrac{p}{m}$ 的概率使得存在 $x$ 使得 $c_x=1$，那么我们得到 $\displaystyle E\min_{x\in T\subseteq S}t_x=\frac{m}{p}$。
  :::::success[证明] 根据题意得出方程：
  $$E\min_{x\in T\subseteq S}t_x=\frac{p}{m}\cdot 1+\frac{m-p}{m}(E\min_{x\in T\subseteq S}t_x+1)$$ 容易解出方程的解。
  ::::: 那么我们就可以设出 DP 状态，设 $f_{i,j}$ 表示考虑到 $t_i$，有 $j$ 个 $[l_i,r_i]$ 与区间有交的方案数（包括乘 $-1$ 的权值），初始条件为 $f_{0,0}=-1$，考虑枚举上一个 $t_{lst}$，设 $k$ 为区间包含 $i$ 但不包含 $lst$ 的区间数，容易得出转移方程：
  $$f_{i,j+k}\leftarrow f_{i,j+k}-f_{lst,j}$$ 现在我们考虑怎么快速求出 $k$，容易容斥发现 $k$ 是区间包含 $i$ 的数量减去区间包含 $[lst,i]$ 的数量，这两个可以预处理二维前缀和实现。
  最后答案就是：
  $$\sum_{i=1}^n\sum_{j=0}^mf_{i,j}\cdot\frac{m}{j}$$ 时间复杂度为 $\Theta(n^2m)$，空间复杂度为 $\Theta(nm)$。
  code