ABC242Ex Random Painting 题解 / Min-Max 容斥学习笔记
:::::info[题目基本信息]
考察：容斥原理，动态规划 DP（
题目简述：
给定序列
- 等概率选取一个整数
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\varnothing}(-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\varnothing] ，容易发现会有\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