【Luogu】 P5643 [PKUWC2018] 随机游走

题目链接

点击打开链接

题目解法

首先考虑 $min-max$ 容斥
可得 $E(S)=\sum _{T\subseteq S}(-1{)}^{|T|-1}f(T)$
其中 $f(T)$ 为从 $x$ 第一次到达 $T$ 集合中任意一点的期望步数
树上随机游走可以想到树上高斯消元，所以开始推式子
记 $g(i,S)$ 为从 $i$ 第一次到达 $S$ 集合中任意一点的期望步数（后面省略 $S$）
$$\begin{gathered} g(i)=1+\frac{1}{de{g}_i}{f}_{fa}+\frac{1}{de{g}_i}\times \sum _{v\in son(i)}{f}_v \\ =1+\frac{1}{de{g}_i}{f}_{fa}+\frac{1}{de{g}_i}\times \sum _{v\in son(i)}(A_v{f}_i+B_v) \\ =1+\frac{1}{de{g}_i}{f}_{fa}+(\frac{1}{de{g}_i}\times \sum _{v\in son(i)}{A}_v)f_i+\frac{1}{de{g}_i}\times \sum _{v\in son(i)}{B}_v \end{gathered}$$
所以 $(1-\frac{1}{de{g}_i}\times \sum _{v\in son(i)}{A}_v)f_i=\frac{1}{de{g}_i}{f}_{fa}+1+\frac{1}{de{g}_i}\times \sum _{v\in son(i)}{B}_v$
把 $f_i$ 的系数除过去即可得到 $A_i,B_i$，式子过于复杂，写了可能也看不清
我们可以钦定 $x$ 为根，那么 $f(S)=B_x$
计算 $f$ 的时间复杂度为 $O(n{2}^n)$

然后我们发现 $min-max$ 容斥的式子是一个子集卷积，直接 $fwt$ 即可，时间复杂度 $O(n{2}^n)$
其实不用 $fwt$ 也可以过题，时间复杂度为 $O(q{2}^n)$，但常数很小

#include 
using namespace std;
const int N=20,P=998244353;
int n,q,rt,f[1<<18],cnt[1<<18],A[N],B[N];
int e[N<<1],ne[N<<1],h[N],idx;
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
inline void inc(int &x,int y){
    x+=y;
    if(x>=P) x-=P;
}
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1) res=1ll*res*a%P;
        a=1ll*a*a%P;
    }
    return res;
}
void dfs(int u,int fa,int S){
	if(S>>u&1) return;
	int rs1=0,rs2=0,deg=(fa>=0);
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];if(v==fa) continue;
		dfs(v,u,S);deg++;
		inc(rs1,A[v]),inc(rs2,B[v]);
	}
    int ivdeg=qmi(deg,P-2);
	rs1=(P+1-1ll*rs1*ivdeg%P)%P,rs1=qmi(rs1,P-2);
	rs2=1ll*rs2*ivdeg%P+1;
	A[u]=1ll*ivdeg*rs1%P,B[u]=1ll*rs2*rs1%P;
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
void fwt(){
    n=1<<n;
    for(int mid=1;mid<n;mid<<=1)
        for(int i=0;i<n;i+=mid<<1)
            for(int j=0;j<mid;j++){
                f[i+j+mid]+=f[i+j];
                if(f[i+j+mid]>=P) f[i+j+mid]-=P;
            }
}
int main(){
	n=read(),q=read(),rt=read();rt--;
	memset(h,-1,sizeof(h));
	for(int i=1;i<n;i++){
		int x=read(),y=read();x--,y--;
		add(x,y),add(y,x);
	}
	for(int S=0;S<1<<n;S++){
		for(int i=0;i<n;i++) A[i]=0,B[i]=0;
		dfs(rt,-1,S),f[S]=B[rt];
		cnt[S]=__builtin_popcount(S)+1;
        if(cnt[S]&1) f[S]=P-f[S];
	}
    fwt();
	while(q--){
		int k=read(),State=0;
		while(k--){ int x=read();State|=1<<(x-1);}
		printf("%d\n",f[State]);
    }
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}
/*
f[i][S]：从i出发，第一个到点集S中的点的期望步数
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73