P5643 [PKUWC2018]随机游走（Min-Max容斥+期望dp+高维前缀和）

木xx木大 · 2021-02-06 11:47:03 · 题解

P5643 [PKUWC2018]随机游走

WC第二课堂的题怎么都这么难了呀，我怎么这么菜连第二课堂都听不懂呀

前置知识：Min-Max 容斥

在本题中，E(\max(S)) 即到达点集中最晚一个点的期望时间，也就是答案；E(\min(T)) 即到达点集中最早一个点的期望时间。而 E(\min(T)) 是比较好做的。

设 f_i 表示从 i 出发到点集中某个点的期望步数，则对于点集中的点，f_i=0；对于点集外的点，f_i=\frac{1}{deg_i}(f_{fa_i}+\sum\limits_{j\in son(i)}f_j)+1。如果暴力高斯消元，复杂度为 O(n^32^n) 。

考虑使用 待定系数法 优化。对于点集外的点，设 f_i=k_if_{fa_i}+b_i；对于点集内的点，显然 k_i=b_i=0

如果把题目给定的出发点看作根，则 f_{rt}=b_{rt}。k_i,b_i 可以按上面的式子 dp 得到

如果每次询问都暴力算，复杂度是 O(q2^n) 的，过不去，所以我们还需要用高维前缀和需处理。总复杂度 O(n2^n+q)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
    int n,m;
    const int N=25,mo=998244353;
    int cnt[1<<N],k[N],b[N],rt,f[1<<N],du[N];
    vector<int> g[N];
    int qpow(int x,int y)
    {
        int s=1;
        while(y)
        {
            if(y&1)s=1ll*s*x%mo;
            x=1ll*x*x%mo;
            y>>=1;
        }
        return s;
    }
    void dfs(int u,int f,int S)
    {
        k[u]=b[u]=0;
        int sumk=0,sumb=0;
        for(auto v:g[u])
            if(v!=f)dfs(v,u,S),sumk=(sumk+k[v])%mo,sumb=(sumb+b[v])%mo;
        if(!((S>>u)&1))k[u]=qpow((du[u]-sumk+mo)%mo,mo-2),b[u]=1ll*(sumb+du[u])*k[u]%mo;
    }
    void work()
    {
        scanf("%d%d%d",&n,&m,&rt),rt--;
        for(int i=1,u,v;i<n;i++)
            scanf("%d%d",&u,&v),u--,v--,g[u].push_back(v),g[v].push_back(u),du[u]++,du[v]++;
        cnt[0]=-1;
        for(int i=1;i<(1<<n);i++)
        {
            cnt[i]=cnt[i>>1]*(i&1?-1:1);
            dfs(rt,n,i);
            f[i]=(b[rt]*cnt[i]+mo)%mo;
        }
        for(int i=0;i<n;i++)
            for(int j=1;j<(1<<n);j++)
                if((j>>i)&1)f[j]=(f[j]+f[j^(1<<i)])%mo;
        while(m--)
        {
            int x,S=0,u;
            scanf("%d",&x);
            while(x--)scanf("%d",&u),S|=(1<<(u-1));
            printf("%d\n",f[S]);
        }
    }
}
int main()
{
    FGF::work();
    return 0;
}