Description

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

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

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

答案对 \(998244353\) 取模。

Solution

题目是让我们求一个集合最后一个中最后一个到达的点的期望，换句话说，就是到达时间的\(max\)的期望

考虑\(MinMax\)容斥：

\[ max\{S\}=\sum_{T⊆S}(-1)^{|T|-1}min\{ T\} \]

这样，我们就只要枚举一下子集就行了。

考虑如何求第一次访问某个集合的时间期望

• 设\(f[i][S]\)表示从\(i\)出发，第一次访问到\(S\)的时间期望

• 显然有如下转移：

• \[ f[i][S]=1+\frac{1}{deg_i}\sum_{j}f[j][S],i和j有边相连 \]

• 这样显然既要考虑父亲还要考虑孩子，不可做，考虑把它化成：

• \[ f[i][S]=A_if[fa_i][S]+B_i \]

• 假设已经知道了所有的\(和A_j和B_j\)，把它带到第一个式子里面，就可以求出\(和A_i和B_i\)啦

• 推导就不说了，注意当\(i\)属于\(S\)时，\(A_i=B_i=0\)，因为\(x\)是根，所以\(f[x][S]=B_x\)

我们再考虑如何求子集和

• 设\(g[i][S]\)表示前\(i\)位与\(S\)相同，后\(N-i\)为是\(S\)的子集的集合的和
• 若\(S\)的第\(i\)为是\(0\)，则\(g[i][S]=g[i+1][S]\)
• 若\(S\)的第\(i\)为是\(1\)，则\(g[i][S]=g[i+1][S]+g[i+1][S - (1<<i)]\)

Code 

#include
    
     using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define mod 998244353inline void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}inline void dec(int &x,int y){x-=y;if(x<0)x+=mod;}inline int fpow(int x,int m){int r=1;for(;m;x=1ll*x*x%mod,m>>=1)if(m&1)r=1ll*r*x%mod;return r;}int N,Q,S,A[1<<18],B[1<<18],d[20],bit[1<<18],f[1<<18];struct edge{int to,nex;}e[40];int en,hr[20];inline void ins(int f,int t){    e[++en]=(edge){t,hr[f]};hr[f]=en;    e[++en]=(edge){f,hr[t]};hr[t]=en;}void dfs(int x,int f,int Set){    if(Set>>x-1&1) return (void)(A[x]=B[x]=0);    register int i;A[x]=B[x]=d[x];    for(i=hr[x];i;i=e[i].nex)if(f^e[i].to)    {        dfs(e[i].to,x,Set);        dec(A[x],A[e[i].to]);        add(B[x],B[e[i].to]);     }    A[x]=fpow(A[x],mod-2);    B[x]=1ll*B[x]*A[x]%mod;}int main(){    N=read();Q=read();S=read();    register int x,y,i,j;    for(i=1;i
     
      >1]+(i&1);        dfs(S,0,i);f[i]=bit[i]&1?B[S]:mod-B[S];    }        for(i=N-1;~i;--i) for(j=(1<
      
       >i&1) add(f[j],f[j^(1<
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！