随机游走 PKUWC2018

[PKUWC2018] 随机游走

水黑。

题目链接： [PKUWC2018] 随机游走 。

题目内容：

给定一棵 nn 个结点的树，你从点 xx 出发，每次等概率随机选择一条与所在点相邻的边走过去。

有 QQ 次询问，每次询问给定一个集合 SS，求如果从 xx 出发一直随机游走，直到点集 SS 中所有点都至少经过一次的话，期望游走几步。

特别地，点 xx（即起点）视为一开始就被经过了一次。

答案对 998244353998244353 取模。

n≤18,Q≤5×103n\le 18,Q\le 5\times10^3 。

首先将 xx 固定为根。

设 tit_i 表示节点 ii 第一次被访问到的期望时间，则询问的答案为 E[max⁡i∈Sti]\mathbb E[\max\limits_{i\in S}t_i] 。

使用 min-max 容斥，则：

E[max⁡S]=∑T⊆S(−1)∣T∣+1E[min⁡T]\mathbb E[\max S]=\sum_{T\subseteq S}(-1)^{|T|+1}\mathbb E[\min T]

由于数据范围较小，我们考虑直接预处理出所有的 E[min⁡T]\mathbb E[\min T] ，使用树形 DP 可以很方便的 O(n)\mathcal{O}(n) 求解。

最后一个 FWT 结束。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=19,M=1<<18,P=998244353;
int n,Q,rt,k[N],b[N],f[M],d[N],G[N<<1],u[N],v[N],deg[N];
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
void dfs(int x,int fa,int S){
    int sum=deg[x],up=deg[x];
    for(int i=d[x];i<d[x+1];i++){
        int u=G[i];
        if(u==fa)continue;
        dfs(u,x,S);
        (sum+=P-k[u])%=P;
        (up+=b[u])%=P;
    }
    k[x]=kpow(sum,P-2);
    b[x]=1ll*up*k[x]%P;
    if((S>>x-1)&1)k[x]=b[x]=0;
}
void init(int S){
    memset(k,0,sizeof(k));
    memset(b,0,sizeof(b));
    dfs(rt,0,S);
    f[S]=(__builtin_popcount(S)&1?b[rt]:(P-b[rt])%P);
}
void FWT(int *f){
    for(int i=2;i<=(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=i)
            for(int k=j;k<j+(i>>1);k++)
                (f[k+(i>>1)]+=f[k])%=P;
}
int main(){
    scanf("%d%d%d",&n,&Q,&rt);
    for(int i=1;i<n;i++)scanf("%d%d",u+i,v+i),d[u[i]]++,d[v[i]]++;
    for(int i=1;i<=n;i++)deg[i]=d[i];
    for(int i=1;i<=n;i++)d[i+1]+=d[i];
    for(int i=1;i<n;i++){
        G[--d[u[i]]]=v[i];
        G[--d[v[i]]]=u[i];
    }
    for(int i=1;i<(1<<n);i++){
        init(i);
    }
    FWT(f);
    while(Q--){
        int K,S=0;
        scanf("%d",&K);
        for(int i=1,x;i<=K;i++)scanf("%d",&x),S|=(1<<x-1);
        printf("%d\n",f[S]);
    }
    return 0;
}