自动搬运

查看原文

来自洛谷，原作者为

	Kelin 这个家伙太菜，没什么可以留下的

搬运于2025-08-24 21:58:57，当前版本为作者最后更新于2018-04-02 20:26:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

给你一幅图,每次给你一个点$u$和一个点集$S$

问从$u$出发走完$S$集合(即$S$内点都至少经过一次)的期望步数

一个点$u$会等概率地走向其相邻的点

---

题解

这玩意是$PKUWC2018D2T3$随机游走的加强版

思路和[HNOI2013]游走类似,也是通过高斯消元来$DP$

考虑设$f[S][i]$表示走完$S$集合,当前在点$i$,然后要把剩下的所有点都走完的期望步数

可以发现,如果询问的是$u,S$那么对应的$f$值就是$f[all-S][u]$

就是相当于把$S$的补集都走完了,然后现在再从$u$把$S$走完的期望

这样如果预处理出$f,$每个询问就可以$O(1)$回答了

这里有个小$trick$就是如果$u\in S$这样就错了,因为$u\notin all-S$

所以对应要求的答案应该是$f[(all-S)|u][u]$

考虑怎么求出$f[S][u]$,初值$f[all]=0$

$flag:$所以这玩意怕不是要倒推

和游走一样列式,$d_u$表示$u$的点度

$$f[S][u]=\frac1{d_u}\sum_{u\to v\in E}f[S|v][v]+1$$

考虑暴力的话就是用高斯消元解这$n2^n$个方程$,$复杂度$O((n2^n)^3)$

这样显然是不行的

考虑到要么$S\subset S|v,$要么$S=S|v,$即$v\in S$

我们把方程分开一下

$$f[S][u]=\frac1{d_u}[\sum_{u\to v\in E,v\in S}f[S][v]+\sum_{u\to v\in E,v\notin S}f[S|v][v]]+1 $$$$f[S][u]-\frac1{d_u}\sum_{u\to v\in E,v\in S}f[S][v]=\frac1{d_u}\sum_{u\to v\in E,v\notin S}f[S|v][v]+1 $$

也就是说,如果我们知道$f[S|v]$的$DP$值那么我们每个状态就只要列$n$个方程

所以按照集合大小倒推,然后每个状态列$n$个方程即可

复杂度$O(n^32^n+\sum n_i)$

#include<bits/stdc++.h>
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
#define go(u) for(register int i=fi[u],v=e[i].to;i;v=e[i=e[i].nx].to)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){return A==B&&(B=(A=ss)+fread(ss,1,1<<17,stdin),A==B)?-1:*A++;}
template<class T>inline void sd(T&x){
    char c;T y=1;while(c=gc(),(c<48||57<c)&&c!=-1)if(c==45)y=-1;x=c-48;
    while(c=gc(),47<c&&c<58)x=x*10+c-48;x*=y;
}
char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
template<class T>inline void we(T x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=19,S=1<<N,P=998244353;
typedef int arr[N];
typedef long long ll;
int n,m,all,f[S][N];arr e,dg,id,pos,inv,ans,Mi,G[N];
inline int fpm(int a,int b){int x=1;for(;b;b>>=1,a=(ll)a*a%P)if(b&1)x=(ll)x*a%P;return x;}
inline int pls(int a,int b){return a+=b,a<P?a:a-P;}
inline int sub(int a,int b){return a-=b,a<0?a+P:a;}
inline void Gauss(int n){
    int mx,t,x;
    fp(i,1,n)fp(j,1,n)G[i][j]=pls(G[i][j],P);
    fp(i,1,n){mx=i;
        fp(j,i,n)if(G[mx][i]<G[j][i])mx=j;
        if(mx^i)fp(j,i,n+1)swap(G[mx][j],G[i][j]);
        x=fpm(G[i][i],P-2);
        fp(j,i+1,n){
            t=(ll)x*G[j][i]%P;
            fp(k,i,n+1)G[j][k]=sub(G[j][k],(ll)t*G[i][k]%P);
        }
    }
    fd(i,n,1){
        fp(j,i+1,n)G[i][n+1]=sub(G[i][n+1],(ll)ans[j]*G[i][j]%P);
        ans[i]=(ll)G[i][n+1]*fpm(G[i][i],P-2)%P;
    }
}
int main(){
    #ifndef ONLINE_JUDGE
        file("s");
    #endif
    sd(n),sd(m);all=(1<<n)-1;int u,v;
    Mi[1]=1;fp(i,2,n)Mi[i]=Mi[i-1]<<1;
    inv[1]=1;fp(i,2,n)inv[i]=(ll)(P-P/i)*inv[P%i]%P;
    while(m--)sd(u),sd(v),e[u]|=Mi[v],e[v]|=Mi[u],++dg[u],++dg[v];
    fd(s,all-1,1){
        int Cnt=0,x,p;
        fp(i,1,n)if(s&Mi[i])id[pos[i]=++Cnt]=i;
        fp(i,1,Cnt){fp(j,1,Cnt)G[i][j]=0;ans[i]=0;}
        fp(i,1,n)if(s&Mi[i]){
            x=inv[dg[i]],p=pos[i];G[p][p]=1,G[p][Cnt+1]=1;
            fp(j,1,n)if(e[i]&Mi[j]){
                if(s&Mi[j])G[p][pos[j]]-=x;
                else G[p][Cnt+1]=pls(G[p][Cnt+1],(ll)x*f[s|Mi[j]][j]%P);
            }
        }
        Gauss(Cnt);
        fp(i,1,Cnt)f[s][id[i]]=ans[i];
    }
    sd(m);
    while(m--){
        static int s;sd(s);u=0;
        while(s--)sd(v),u|=Mi[v];sd(v);
        we(f[(all^u)|Mi[v]][v]);
    }
return Ot(),0;
}