题解 P5643 【[PKUWC2018]随机游走】

Marser

2019-11-12 08:04:48

题解

题意

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

有 q 次询问，每次询问给定一个集合 S，求如果从 x 出发一直随机游走，直到点集 S 中所有点都至少经过一次的话，期望游走几步。特别地，点 root （即起点）视为一开始就被经过了一次。

题解

一般的随机游走问题，由于后效性，必须考虑列方程组，通过高斯消元求解。但是，这题是树上的随机游走问题，只能从父亲与儿子转移，可以考虑直接dp。
由于本题要求点集 S 中所有点都被经过的步数期望，即到达点集 S 中最后一个点的期望步数。运用\min-\max容斥可以将其转化为到达点集 S 中第一个点的期望步数。
设 f_{S,i} 表示从 i 出发，经过 S 中的至少一个点的期望步数，deg_i 为点 i 的度数，可以得到这样的递推式：

\begin{aligned} f_{S,i} & = \frac{1}{deg_i} (f_{S,fa_i} + 1 + \sum_{v \in son_i} (f_{S,v}+1)) \\ & = \frac{1}{deg_i} (f_{S,fa_i} + \sum_{v \in son_i} f_{S,v}) + 1 \end{aligned}

若 i \in S ，则 f_{i,S} = 0。

按照套路，将转移方程写成有关于父亲的函数，即f_{S,i} = A_i \times f_{S,fa_i} + B_i，分离儿子与父亲的贡献。

\begin{aligned} f_{S,i} & = \frac{1}{deg_i} (f_{S,fa_i} + \sum_{v \in son_i} f_{S,v}) + 1 \\ & = \frac{1}{deg_i} (f_{S,fa_i} + \sum_{v \in son_i} (A_v \times f_{S,i}+B_v)) + 1 \\ & = \frac{1}{deg_i} (f_{S,fa_i} + (\sum_{v \in son_i} A_v) \times f_{S,i} + \sum_{v \in son_i} B_v) + 1 \\ & =\frac{1}{deg_i} (f_{S,fa_i} + sumA_v \times f_{S,i} + sumB_v) + 1\\ deg_i \times f_{S,i} & = f_{S,fa_i} + sumA_v \times f_{S,i} + sumB_v +deg_i \\ (deg_i - sumA_v) \times f_{S,i} & = f_{S,fa_i} + sumB_v + deg_i \\ f_{S,i} & = \frac{1}{deg_i - sumA_v} f_{S,fa_i} + \frac{sumB_v + deg_i}{deg_i - sumA_v} \\ A_i & = \frac{1}{deg_i - sumA_v} , B_i = \frac{sumB_v + deg_i}{deg_i - sumA_v}\end{aligned}

发现 A_i,B_i 的方程与父亲无关，可以直接树形dp求解。由于 root 不能从父亲转移，显然有f_{S,root} = B_{root} 。
所以点集 S 的答案为 \sum_{T \in S,T \not= \varnothing} (-1)^{|T|+1} f_{T,root}。
预处理所有f_{S,root}可以做到\mathcal{O}(q2^n)，由于本题数据太水，可以通过。

但是这样做很不优美，我们考虑一些更加优雅的做法。
考虑集合或卷积的形式：

C_i = \sum_{j|k = i} A_j \times B_k

我们计\widehat{C_i} = \sum_{j \in i} C_j，类似定义\widehat{A_i},\widehat{B_i}。

\begin{aligned} \widehat{C_i} & = \sum_{j|k \in i} A_j \times B_k \\ & = \sum_{j \in i , k \in i} A_j \times B_k \\& = (\sum_{j \in i} A_j) \times (\sum_{j \in i} B_j) \\& = \widehat{A_i} \times \widehat{B_i}\end{aligned}

所以，经过FWT集合或卷积变换后，新多项式是原多项式的子集和。
可以运用单次FWT预处理所有子集和，复杂度 \mathcal{O}(n2^n) 。

代码

#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=19;
const int mod=998244353;
int to[MN<<1],nxt[MN<<1],h[MN],cnt;
inline void ins(int s,int t){
    to[++cnt]=t;nxt[cnt]=h[s];h[s]=cnt;
    to[++cnt]=s;nxt[cnt]=h[t];h[t]=cnt;
}
inline ll qpow(ll a,ll b){
    reg ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;b>>=1;
    }
    return res;
}
int deg[MN],A[MN],B[MN];
void dfs(int st,int fa,int S){
    reg int totA=0,totB=0,inv=0;
    if(S&(1<<st-1))return;
    for(reg int i=h[st];i;i=nxt[i])
        if(to[i]!=fa){
            dfs(to[i],st,S);
            totA=(totA+A[to[i]])%mod;
            totB=(totB+B[to[i]])%mod;
        }
    inv=qpow((deg[st]-totA+mod)%mod,mod-2);
    A[st]=inv;B[st]=1ll*inv*(totB+deg[st])%mod;
}
int n,q,root,U,F[1<<18|5],Ans;
int main(){
    scanf("%d%d%d",&n,&q,&root);
    for(reg int i=1,s,t;i<n;i++){
        scanf("%d%d",&s,&t),ins(s,t);
        deg[s]++;deg[t]++;
    }
    U=1<<n;
    for(reg int S=1;S<U;S++){
        for(reg int i=1;i<=n;i++)A[i]=B[i]=0;dfs(root,0,S);
        F[S]=(((__builtin_popcount(S)&1)?1:-1)*B[root]+mod)%mod;
    }
    for(reg int i=1;i<U;i<<=1)
        for(reg int len=i<<1,j=0;j<U;j+=len)
            for(reg int k=0;k<i;k++)
                F[i+j+k]=(F[i+j+k]+F[j+k])%mod;
    while(q--){
        static int k,S;scanf("%d",&k);S=0;
        for(reg int i=1,x;i<=k;i++)
            scanf("%d",&x),S|=(1<<x-1);
        printf("%d\n",(F[S]+mod)%mod);
    }
    return 0;
}