[PKUWC 2018] 随机游走

LOJ #2542.

思路

我们大胆猜想一下,这个题显然可以Min-Max容斥做。$\min(S)$就是访问$S$中的第一个节点的期望时间,$\max(S)$就是访问$S$中的最后一个节点的期望时间,则根据Min-Max容斥很显然有$$\max(S)=\sum \limits_{\emptyset\not =T\subseteq S}(-1)^{|T|+1}\min(T)$$

所以我们的工作就变成了处理出所有的$\min(T)$

设$f_x$表示第一次到点$x$时的期望步数,$fa_x$为$x$的父亲,$y$为$x$的儿子们,$d_x$为$x$的度数,则有转移方程
$$f_x=\frac{f_{fa_x}+\sum f_y}{d_x}+1$$
据说有一种套路,在树上算期望的时候,$f_x$可以表示为$$f_x=A_x\cdot f_{fa_x}+B_x$$
试图把这个形式往上边的式子里带,得到
$$\begin{split}
f_x&=\frac{f_{fa_x}+\sum \left( A_y\cdot f_x+B_y\right)}{d_x}+1\\
(1-\frac{\sum A_y}{d_x})\cdot f_x&=\frac{f_{fa_x}+\sum B_y}{d_x}+1\\
f_x&=\frac{f_{fa_x}+\sum B_y}{d_x}\cdot \frac{d_x}{d_x-\sum A_y}+ \frac{d_x}{d_x-\sum A_y}\\
f_x&=\frac{f_{fa_x}+\sum B_y+d_x}{d_x-\sum A_y}\\
f_x&=\frac{1}{d_x-\sum A_y}\cdot f_{fa_x}+\frac{\sum B_y+d_x}{d_x-\sum A_y}
\end{split}$$
即$$\begin{split}
A_x&=\frac{1}{d_x-\sum A_y}\\
B_x&=\frac{\sum B_y+d_x}{d_x-\sum A_y}
\end{split}$$

假设当前枚举到一个集合$S$,要求从$x$第一次到$S$中的点的期望时间,只要把$x$设为根,把$S$中所有的点都设为起点,DP一下就可以了

代码

#include <iostream>
#include <cstdio>

template <typename T> void in(T &_){
    char c=getchar(); while(c<'0'||c>'9') c=getchar();
    _=0; while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar();
}
template <typename T, typename ...A> void in(T &_, A &...a){in(_); in(a...);}

struct Node{
    struct Edge *head;
    bool fl;
    int A, B, deg;
}node[25];

struct Edge{
    Node *to; Edge *ne;
    Edge(int x, int y) : to(node+y), ne(node[x].head){}
};

const int MOD=998244353;
int N, Q, S, siz[1<<18], f[1<<18];

int ksm(int x, int y){
    int z=1;
    for(; y; y>>=1, x=1LL*x*x%MOD) z=(y&1)?1LL*x*z%MOD:z;
    return z;
}

void dfs(Node *x, Node *fa){
    if(x->fl){x->A=0, x->B=0; return;}
    int A=0, B=0;
    for(Edge *i=x->head; i; i=i->ne) if(i->to!=fa){
        dfs(i->to, x);
        A=(A+i->to->A)%MOD; B=(B+i->to->B)%MOD;
    }
    int inv=ksm((x->deg-A)%MOD, MOD-2); 
    x->A=inv, x->B=1LL*(x->deg+B)%MOD*inv%MOD;
}

int main(){
    int x, y;
    in(N, Q, S);
    for(int i=1; i<N; i++){
        in(x, y);
        node[x].head=new Edge(x, y); node[x].deg++;
        node[y].head=new Edge(y, x); node[y].deg++;
    }
    for(int i=0; i<(1<<N); i++){
        for(int j=1; j<=N; j++) node[j].fl=(i>>(j-1))&1;
        dfs(node+S, NULL); f[i]=node[S].B;
        siz[i]=siz[i>>1]+(i&1);
    }
    while(Q--){
        int sta=0, ans=0;
        in(x); while(x--) in(y), sta|=1<<(y-1);
        for(int i=sta; i; i=sta&(i-1)) ans=(ans+((siz[i]&1)?1LL:-1LL)*f[i])%MOD;
        printf("%d\n", (ans+MOD)%MOD);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注