【Luogu】 P5643 [PKUWC2018] 随机游走

本文主要是介绍【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 <bits/stdc++.h>
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中的点的期望步数
*/

这篇关于【Luogu】 P5643 [PKUWC2018] 随机游走的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---