[PKUWC2018]随机游走题解

感谢朱神的指导！

Statement

[P5643 PKUWC2018]随机游走 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

突然发现自己对于 min-max 容斥的理解是错的，一直没有去深究当 min-max 外面套了个期望之后到底变成了什么东西，不管不顾，强行套用 $E(\max/\min(S))$ 意义做题

想当然地认为：

$E(\min(S))$ 表示随便走到集合 $S$ 中某一个点的期望时间，那么设 $dp_i$ 表示从根走到 $i$ 的期望步数，那么 $E(\min(S))=\min_\limits{i\in S}dp_i$ ，显然 $dp_i$ 容易高斯消元求出

不得不说这个想法的确有点 naive ，错误在于，由于 $\min(S)$ 其实是一个随机变量，显然直接取 min 值在期望的意义上是完全行不通的。

题目要求的是 “走完给定集合 $\mathbf S$ 至少一次的期望步数” . 所以我们应当考虑 , 走完某个集合 $S$ 的期望步数 , 并进行转移 .

欲求期望 , 首先需要有 "随机变量" . 对于某个集合 $S$ , 我们有很多不同的路径走完它 , 所以我们的 "随机变量" 设为一个对应于该路径 $path_{S}$ 的集合 $S' $ : 储存到达 $S$ 中所有点的步数 . 显然对于一个确定的集合 $S$ 和确定的路径 $path_{S}$ , $S^{\prime}$ 也是唯一确定的 . 那么我们发现 ,$ S'$ 中的最大值表示的是到达 $S$ 中最后一个点 的步数 , 也就是走完 $S$ 的步数 . 而最小值表示的是第一次到达 $S$ 中的点的步数

—— zyc2003

于是明白了必须要把 $S$ 放入状态里面，设 $dp_{i,s}$ 表示从 $i$ 出发，走到 $s$ 中任何一个点的期望步数，那么

\[dp_{i,s}=\frac 1{deg_i}\sum_{(v,i)}dp_{v,s}+1 \]

问题仍然在于后效性的处理，现在高斯消元肯定是不行的了

下面我们简写 $dp_{i,s}$ 为 $dp_i$ ，反正第二维不影响我们转移

这里出现了一个重要的我不知道的“常用技巧”：

我们想让 $dp_{i}$ 的转移仅仅和 $dp_{f}$ （ $f$ 表示 $i$ 的父亲）

所以，我们设 $dp_i=a_i dp_f+b_i$ ，然后探求 $a,b$ 数组的关系

显然这里不会出现二次函数及以上的关系，毕竟我们的转移方程只涉及加

据说这个叫 树上高斯消元

我们不妨把这个玩意带入：

\[\begin{align*} deg_idp_i&=deg_i+dp_f+\sum_{v\in son}dp_v\\ &=deg_i+dp_f+\sum_{v\in son}a_vdp_u+\sum_{v\in son}b_v\\ \end{align*} \]

所以，

\[(deg_i-\sum_{v\in son}a_v)dp_u=dp_f+deg_i+\sum_{v\in son }b_v \]

简记 $suma=\sum_{v\in son}a_v,sumb=\sum_{v\in son}b_v$，所以

\[dp_u=\frac1{deg_i-suma}dp_f+\frac{deg_i+sumb}{deg_i-suma} \]

\[a_u=\frac 1{deg_i-suma},b_u=\frac{deg_i+sumb}{deg_i-suma} \]

容易发现 $a,b$ 数组可以递推出来，叶子节点的 $a=1,b=0$ 即可

所以，我们 $O(2^n)$ 枚举第二维 $s$ ,每一次递推 $a,b$ 的时候，如果当前的 $i\in s$ 就直接 $ban$ 掉即可，毕竟我们只关心根的 $a,b$ 值（具体可以看代码），总之，复杂度 $O(n2^n\log)$ ，$log$ 是快速幂求逆元

我们有 $dp_{root,s}=b_{root}$

好的，显然， $E(\min(s))=dp_{root,s}$

所以对于每一次询问 $S$ ，答案为 $\sum_{T\subseteq S}(-1)^{|T|-1}dp_{root,T}$ ，复杂度 $O(q2^n)$ ，我们还想更优雅

由于 min_max 容斥和 fwt 是好兄弟 ，所以我们考虑 fwt

设 $g_T=(-1)^{|T|-1}dp_{root,T}$ ，那么 $ans_S=\sum_{T\subseteq S}g_T$，这显然就是 fwt

所以最终复杂度 $O(n2^nlog)$

Code

#include
#define int long long
using namespace std;
const int N = 20;
const int mod = 998244353;

int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

int a[N],b[N],f[1<<18|5],deg[N];
vectorEdge[N];
int n,q,x,k,s;

int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
void dfs(int u,int fath,int s){
    if(s&(1<>1;j<(1<


						
							

						
							
							
			数论——概率期望数论——快速变换数论——minmax容斥

[PKUWC2018]随机游走题解

Statement

Solution

Code

相关

标签

[PKUWC2018]随机游走 题解

Statement

Solution

Code

相关

标签

[PKUWC2018]随机游走题解