前言
到这里PKUWC2018的题目，斗地主不是题目，就算都补完了，希望今年的PKUWC可以有好运吧。
题目链接
做法
显然可以Min-Max容斥，不会的戳这儿。
我们要求的是$Max(S)$，所以我们考虑$Min(S)$如何计算。
$Min(S)$实际上求的就是从起点出发，走到S中任意一个点的期望时间。
我们枚举S，以$f_i$表示从i出发走到S中任意一个点的期望时间，$d_i$表示i这个点的度。
如果$i\in S$，那么$f_i=0$，否则$f_i=\frac{\sum\limits_{i\to j}f_j}{d_i}+1$
那么我对这些方程高斯消元，复杂度$2^n*n^3$过大。
发现这个消元实际上是在树上进行，那么我们用树上消元的经典trick来解决。
将$f_i$用$k_i*f_{fa(i)}+b_i$表示，那么我们将原方程变形。
$d_i*f_i=\sum\limits_{j\in son_i}f_j+f_{fa(i)}+d_i$
再将$f(j)$全部用$k_j*f_i+b_j$替换，用$kk$表示$\sum\limits_{j\in son_i}k_j$，$bb$表示$\sum\limits_{j\in son_i}b_j$
那么可以得到$d_i*f_i=kk*f_i+bb+f_{fa(i)}+d_i$
再将$f(i)$用$k_i*f_{fa(i)}+b_i$替换，移项。
$(d_i-kk)*k_i*f_{fa(i)}+(d_i-kk)*b_i=bb+f_{fa(i)}+d_i$
左右两边恒等，这样我们就能解出$k_i$和$b_i$了。
根节点的$f_{fa(i)}$为0，所以根节点$f_i=b_i$，而我们只需要起点的f，所以把起点提到根，做一遍上述的消元就解出了所有的$Min(S)$
由于Min-Max容斥本质上是个带系数的子集卷积。
$Max(S)=\sum\limits_{S’\subseteq S}Min(S’)*(-1)^{|S’|-1}$
如果$|S’|$是偶数的话我们把它的系数变为-1，用$FWT$做一遍子集前缀和就行了，回答变为$O(1)$，而$|S’|$就是$S’.popcount()$
总复杂度$O(2^n*n+Q)$
代码
1 |
|