洛谷 P4321 【随机漫游】

题目大意

给出(n(nleq 18))个点的无向连通图，(m(mleq 10^5))次询问。每次询问给出一个点集和一个起点(s)，询问从(s)出发，经过这个点集中的每一个点至少一次的期望步数。

题目分析

经过这个点集每一个点至少一次的期望步数，就是到达点集最后一个点的期望步数。这个直接算貌似不好求，考虑min-max容斥。

对于每一个起点，(max(S)=sumlimits_{T subseteq S}(-1)^{|T|-1}min(T))

(max(S))表示到达点集(S)中的最后一个点的期望步数。

(min(S))表示到达点集(S)中的最初一个点的期望步数。

怎么求(min(T))呢？

枚举集合(T)，设其补集为(C)，设对于点(x)的(min(T))为(f_x)。

对于(T)中的点(x)，显然(f_x=0)

对于(C)中的点(x)，(f_x=frac{1}{d_x}sumlimits_{(x,y)in E}f_y+1)

那么就可以高斯消元了。

如何快速计算(max(S))呢？

FWT(O(n* 2^n))计算子集贡献已经是常规操作了。