题解：P4321 随机漫游

随机游走板子？

q

次询问，给出点

u

和点集

S

，求从

u

出发随机游走刚好走过

S

的所有点的期望步数，也就是经过

S

中的某个点所用步数的最大的期望值，记为

E_u(\max (S))

。

套路地考虑 min-max 容斥，

\displaystyle E_u(\max(S))=\sum_{T\subseteq S} (-1)^{|T|+1} E_u(\min(T))

考虑对于固定的

T

，对于所有

u

求出

E_u(\min(T))

。

设

f_{u}=E_u(\min(T))

，容易得出以下转移，

f_{u}= \begin{cases} 0 & u\in T\\ 1+\displaystyle\sum_{(u,v)\in E} \frac{1}{d_u}f_v & u\not\in T \end{cases}

显然转移存在环，不过可以列出一个

n

个方程的

n

元线性方程组，那么可以用高斯消元法

O(n^3)

求出所有

f_u

，进而得到所有

E_u(\min(T))

，这一部分时间复杂度

O(n^3 2^n)

。

然后就要求

E_u(\max(S))

了，发现容斥系数只与

|T|

有关，直接对于每个点

u

，让所有

E_u(\min(T))

带着容斥系数做高维前缀和即可。一共做

n

遍高维前缀和，复杂度

O(n2^n)

。

在代码里，高维前缀和用 FWT 实现。

CPP

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()

#define N 21
#define S (1<<18)+91
#define int long long
#define pcnt __builtin_popcount

const int mod=998244353;
int n,m,q,tot,a[N][N],d[N],f[N][S];
vector<int>e[N];

inline int qpow(int a,int b=mod-2){
    int ans=1;

    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }

    return ans;
}

inline void fwt(int *f,int n){
    int len=2,nx=1;

    while(len<=n){
        int i=0;
        while(i<n){
            rep(j,0,nx-1){
                f[i+j+nx]=(f[i+j+nx]+f[i+j])%mod;
            }
            i+=len;
        }

        len<<=1;
        nx<<=1;
    }
}

inline void gauss(int n){
    rep(i,1,n){
        if(!a[i][i]){
            continue;
        }

        int iv=qpow(a[i][i])%mod;

        rep(j,1,n){
            if(i==j){
                continue;
            }

            int c=a[j][i]*iv%mod;

            if(!c){
                continue;
            }

            rep(k,i,n+1){
                a[j][k]=(a[j][k]-c*a[i][k]%mod+mod)%mod;
            }
        }
    }

    rep(i,1,n){
        a[i][n+1]=a[i][n+1]*qpow(a[i][i])%mod;
    }
}

inline int ng(int x){
    return x&1?mod-1:1;
}

inline void init(){
    rep(s,1,tot){
        rep(i,1,n){
            rep(j,1,n+1){
                a[i][j]=0;
            }
        }

        rep(i,1,n){
            if(s>>(i-1)&1){
                a[i][i]=1;
            }
            else{
                int iv=d[i];
                a[i][i]=1;
                a[i][n+1]=1;

                for(int x:e[i]){
                    a[i][x]=(-iv+mod)%mod;
                }
            }
        }

        gauss(n);

        rep(i,1,n){
            f[i][s]=a[i][n+1]*ng(pcnt(s)+1)%mod;
        }
    }
}

signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m;

    rep(i,1,m){
        int u,v;
        cin>>u>>v;

        e[u].pb(v);
        e[v].pb(u);

        d[u]++,d[v]++;
    }

    rep(i,1,n){
        d[i]=qpow(d[i]);
    }

    tot=(1<<n)-1;

    init();

    rep(i,1,n){
        fwt(f[i],1<<n);
    }

    cin>>q;

    rep(i,1,q){
        int s=0,c,u;
        cin>>c;

        rep(j,1,c){
            int x;
            cin>>x;

            s|=1<<(x-1);
        }

        cin>>u;

        cout<<f[u][s]<<'\n';
    }

    return 0;
}

题解：P4321 随机漫游

文章操作

相关推荐

评论

题解：P4321 随机漫游