题解：P4321 随机漫游
Lucyna_Kushinada
·
·
题解
随机游走板子？
套路地考虑 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;
}
```