首页 > 其他 > 详细

「PKUWC2018」随机游走

时间:2019-06-13 14:26:54      阅读:89      评论:0      收藏:0      [点我收藏+]

题意

给定一棵 \(n\) 个结点的树,你从点 \(x\) 出发,每次等概率随机选择一条与所在点相邻的边走过去。
\(Q\) 次询问,每次询问给定一个集合 \(S\),求如果从 \(x\) 出发一直随机游走,直到点集 \(S\) 中所有点都至少经过一次的话,期望游走几步。
\(1\leq n\leq 18\)\(1\leq Q\leq 5000\) .

Solution

题意即为求集合中最后一个点被访问的期望时间。考虑 \(\text{min-max}\) 容斥,转化为第一个点被访问的期望时间 \(E(\min(S))\)

\(2^n\) 枚举所有子集 \(S\) ,设 \(f(u)\) 表示从 \(u\) 号点出发第一次走到子集 \(S\) 中的点的期望时间。若 \(u\) 在集合中则 \(f(u)=0\) ,否则
\[ f(u)=1+d_uf(fa_u) +d_u(\sum f(ch_u)) \]
(其中 \(d_u=\frac{1}{deg[u]}\)\(deg[u]\) 表示 \(u\) 的度数。 )

\(f_u=k_uf(fa_u)+b_u\)

\(sk_u=\sum k_{ch_u}, sb_u=\sum b_{ch_u},\)
\[ f(u)=1+d_uf(fa_u) +d_u(sk_uf(u)+sb_u) \(1-sk_u)f(u)=d_uf(fa_u)+d_usb_u+1 \]

由上式可得:
\[ k_u=\frac{d_u}{1-sk_u}, b_u=\frac{d_usb_u+1}{1-sk_u} \]

故我们直接一边 dfs 即可求出。

最后高维前缀和求 \(E(\max(S))\) ,询问直接输出即可。复杂度 \(O(n\cdot 2^n)\)

#include<bits/stdc++.h>
const int N=21,M=(1<<18)+5,Mod=998244353;
int head[N],nxt[N<<1],to[N<<1],n,q,x,s,d[N],f[M],k[N],b[N];
inline int mul(int x, int y) { return 1ll*x*y%Mod; }
inline int po(int x, int y)
{
    int r=1;
    while(y)
    {
        if(y&1) r=mul(r,x);
        x=mul(x,x), y>>=1;
    }
    return r;
}
void addedge(int u, int v, int now) {
    nxt[now]=head[u], head[u]=now, to[now]=v;
}
void dfs(int u, int fa)
{
    k[u]=b[u]=0;
    if(s&(1<<u-1)) return ;
    int sk=0,sb=0;
    for(int e=head[u];e;e=nxt[e])
    {
        if(to[e]==fa) continue;
        dfs(to[e],u);
        sk=(sk+k[to[e]])%Mod,sb=(sb+b[to[e]])%Mod;
    }
    int tmp=po(Mod+1-mul(d[u],sk),Mod-2);
    k[u]=mul(d[u],tmp),b[u]=mul(mul(d[u],sb)+1,tmp);
}
int main()
{
    scanf("%d%d%d",&n,&q,&x);
    for(int i=1;i<n;++i)
    {
        int u,v; scanf("%d%d",&u,&v);
        addedge(u,v,i*2-1);
        addedge(v,u,i*2);
        ++d[u],++d[v];
    }
    for(int i=1;i<=n;++i) d[i]=po(d[i],Mod-2);
    for(s=1;s<(1<<n);++s)
    {
        dfs(x,x);
        f[s]=__builtin_popcount(s)&1?b[x]:Mod-b[x];
    }
    for(int i=0;i<n;++i)
        for(int j=0;j<(1<<n);++j)
            if(j&(1<<i)) f[j]=(f[j]+f[j^(1<<i)])%Mod;
    while(q--)
    {
        int k,now=0; scanf("%d",&k);
        for(int i=1;i<=k;++i)
        {
            int x; scanf("%d",&x);
            now|=(1<<x-1);
        }
        printf("%d\n",f[now]);
    }
}

「PKUWC2018」随机游走

原文:https://www.cnblogs.com/farway17/p/11015874.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!