loj#2542. 「PKUWC 2018」随机游走

62 阅读 0 评论 41 点赞

我是靠谱客的博主甜美网络，最近开发中收集的这篇文章主要介绍loj#2542. 「PKUWC 2018」随机游走，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

解题思路：

Min-Max容斥真神奇……然而不知如何证明……

设 $Max(s)$ 表示集合里最晚被访问的节点被访问的期望步数（也就是访问所有节点的期望步数）。

设 $Min(s)$ 表示集合里最早被访问的节点被访问的期望步数（也就是第一次访问到集合里的节点的期望步数）

那么 $Max(s)=sumlimits_{Tin S}(-1)^{|T|+1}Min(T)$

$Min(S)$ 是比较好算的，令 $f_{i,S}$ 表示从 $i$ 出发，第一次访问 $S$ 里的节点的期望步数，根据树形期望dp的老套路， $f_{i,S}$ 可以表示成 $k_if_{fa}+b_i$ 的形式，推一推转移式dfs即可。

注意最后统计子集和不要枚举子集，有 $O(n2^n)$ 的方法。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int getint()
{
    ll i=0,f=1;char c;
    for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
    if(c=='-')c=getchar(),f=-1;
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}
const int N=20,mod=998244353;
int n,Q,X,S,bin[1<<18];
ll f[1<<18],k[N],b[N];
int tot,du[N],first[N],nxt[N<<1],to[N<<1];
inline void add(ll &x,ll y){x=x+y>=mod?x+y-mod:x+y;}
inline void dec(ll &x,ll y){x=x-y<0?x-y+mod:x-y;}
ll Pow(ll x,int y)
{
    ll res=1;
    for(;y;y>>=1,x=x*x%mod)
        if(y&1)res=res*x%mod;
    return res;
}
inline void add(int x,int y)
{
    nxt[++tot]=first[x],first[x]=tot,to[tot]=y,du[y]++;
}
void dfs(int u,int fa,int s)
{
    if(s&(1<<u-1)){k[u]=b[u]=0;return;}
    k[u]=b[u]=du[u];
    for(int e=first[u];e;e=nxt[e])
    {
        int v=to[e];if(v==fa)continue;
        dfs(v,u,s);
        dec(k[u],k[v]),add(b[u],b[v]);
    }
    k[u]=Pow(k[u],mod-2),b[u]=b[u]*k[u]%mod;
}
int main()
{
    //freopen("lx.in","r",stdin);
    n=getint(),Q=getint(),X=getint(),S=1<<n;
    for(int i=1;i<S;i++)bin[i]=bin[i>>1]+(i&1);
    for(int i=1;i<n;i++)
    {
        int x=getint(),y=getint();
        add(x,y),add(y,x);
    }
    for(int s=1;s<S;s++)
        dfs(X,0,s),f[s]=bin[s]&1?b[X]:mod-b[X];
    for(int i=1;i<S;i<<=1)
        for(int j=0;j<S;j++)if(j&i)add(f[j],f[j^i]);
    while(Q--)
    {
        int q=getint(),s=0;
        while(q--)s|=(1<<getint()-1);
        cout<<f[s]<<'n';
    }
    return 0;
}