出题人:Cai 大佬
题目大意: 一张 $n$个点 $m$条边的无向图, 有 $Q$个询问, 每次给出点集 $S$和起点 $x$, 求从起点出发向四周等概率游走, 期望走几步走完点集中的点.
数据范围:$n \leq 18,Q \leq 100000$, 时限 3 秒

分层高消

以下大写字母表示一个点集, 小写字母表示一个点
所谓分层高消，就是每进行一次高斯消元，就利用当前高斯消元的结果，构造新的方程矩阵进行高斯消元，以达到优化时间复杂度的目的。
$f(x,S)$表示从 $x$出发, 已经走过了点集 $S$, 走遍全图的期望。
由于每次走一个新的点，已经走过的点集只可能扩大不可能缩小，所以我们可以利用这个性质进行分层。每次高斯消元是用于求出 $f(x,S)$的。
对于一个在 $S$集中的点 $x$（由于 $x$是起点，所以可以看作走过了），设 $du(x)$为 $x$的度数，列出方程
$ f(x,S) = \frac{1}{du(x)} (f(y,S) \times [ y \in S ]+ f(y,S \cup {j } ) \times [ y \not\in S ] )$$
做高消即可，复杂度 $O(n^3 2^n+Q)$

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,Q;const int mod=998244353;
int e[19][19],du[19],bin[19],a[19][19],f[19][(1<<18)],b1[19],b2[19];
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void gauss(int tot) {
    for(int k=1;k<=tot;++k) {
        int id=k;while(!a[id][k]&&id<tot) ++id;
        if(id!=k) swap(a[id],a[k]);
        int tmp=ksm(a[k][k],mod-2);
        for(int j=k;j<=tot+1;++j) a[k][j]=1LL*a[k][j]*tmp%mod;
        for(int i=1;i<=tot;++i) {
            if(i==k) continue;
            tmp=a[i][k];
            for(int j=k;j<=tot+1;++j)
                a[i][j]=(a[i][j]+mod-1LL*a[k][j]*tmp%mod)%mod;
        }
    }
}
void init() {
    for(int no=bin[n]-2;no>=0;--no) {
        int tot=0;
        for(int i=0;i<n;++i) if(no&bin[i]) b1[i]=++tot,b2[b1[i]]=i;
        for(int i=1;i<=tot;++i)
            for(int j=1;j<=tot+1;++j) a[i][j]=0;
        for(int i=0;i<n;++i) if(no&bin[i]){
            a[b1[i]][b1[i]]=1,a[b1[i]][tot+1]=1;int ni=ksm(du[i],mod-2);
            for(int j=0;j<n;++j) {
                if(!e[i][j]) continue;
                if(no&bin[j]) a[b1[i]][b1[j]]=mod-ni;
                else a[b1[i]][tot+1]=(a[b1[i]][tot+1]+1LL*f[j][no|bin[j]]*ni%mod)%mod;
            }
        }
        gauss(tot);
        for(int i=1;i<=tot;++i) f[b2[i]][no]=a[i][tot+1];
    }
}
int main()
{
    freopen("gemo.in","r",stdin);
    freopen("gemo.out","w",stdout);
    int x,y,num;
    n=read(),m=read();
    for(int i=1;i<=m;++i)
        x=read()-1,y=read()-1,e[x][y]=e[y][x]=1,++du[x],++du[y];
    bin[0]=1;for(int i=1;i<=n;++i) bin[i]=bin[i-1]<<1;
    init(),Q=read();
    while(Q--) {
        num=read();int S=0;
        for(int i=1;i<=num;++i) x=read()-1,S|=bin[x];
        x=read()-1,printf("%d\n",f[x][((bin[n]-1)^S)|bin[x]]);
    }
    return 0;
}

max-min 容斥

max-min 容斥就是下面这个式子：
$$max(S)=\sum (-1)^{|S’|-1} min(S’) (S’ \subset S)$$
然后呢，我们就把若干个点里，期望最晚到其中的某个点这个问题转化为若干个点里，期望最早到其中的某个点了。这样的话枚举点集做高斯消元，复杂度是 $O(2^n n^3)$
然后可以把大小为偶数的子集和都取相反数，利用一点黑科技很快求出子集和：（每次求出当前集合去掉小于 j 的若干元素后的子集的和）

for(int j=0;j<n;++j)//必须先枚举 j，以免重复计算一个集合
    for(int zt=0;zt<=bin[n]-1;++zt)
    if(zt&bin[j]) f[i][zt]=(f[i][zt]+f[i][zt^bin[j]])%mod;

总复杂度就是 $O(2^n n^3 +2^n n+Q)$的了。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,Q;const int mod=998244353;
int e[19][19],du[19],bin[19],a[19][19],f[19][(1<<18)],b1[19],b2[19];
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void gauss(int tot) {
    for(int k=1;k<=tot;++k) {
        int id=k;while(!a[id][k]&&id<tot) ++id;
        if(id!=k) swap(a[id],a[k]);
        int tmp=ksm(a[k][k],mod-2);
        for(int j=k;j<=tot+1;++j) a[k][j]=1LL*a[k][j]*tmp%mod;
        for(int i=1;i<=tot;++i) {
            if(i==k) continue;
            tmp=a[i][k];
            for(int j=k;j<=tot+1;++j)
                a[i][j]=(a[i][j]+mod-1LL*a[k][j]*tmp%mod)%mod;
        }
    }
}
void init() {
    for(int zt=0;zt<bin[n]-1;++zt) {//最早走到 zt 外的点的期望
        int tot=0;
        for(int i=0;i<n;++i) if(zt&bin[i]) ++tot,b1[i]=tot,b2[tot]=i;
        for(int i=1;i<=tot;++i)
            for(int j=1;j<=tot;++j) a[i][j]=0;
        for(int i=0;i<n;++i) {
            if(!(zt&bin[i])) continue;
            a[b1[i]][b1[i]]=1,a[b1[i]][tot+1]=1;int ni=ksm(du[i],mod-2);
            for(int j=0;j<n;++j)
                if(e[i][j]&&(zt&bin[j])) a[b1[i]][b1[j]]=mod-ni;
        }
        gauss(tot);
        for(int i=1;i<=tot;++i) f[b2[i]][(bin[n]-1)^zt]=a[i][tot+1];
    }
    for(int zt=0;zt<bin[n]-1;++zt) {
        int js=0;
        for(int i=0;i<n;++i) if(zt&bin[i]) ++js;
        if(!(js&1)) for(int i=0;i<n;++i) f[i][zt]=mod-f[i][zt];//取相反数
    }
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
        for(int zt=0;zt<=bin[n]-1;++zt)
        if(zt&bin[j]) f[i][zt]=(f[i][zt]+f[i][zt^bin[j]])%mod;
}
int main()
{
    freopen("gemo.in","r",stdin);
    freopen("gemo.out","w",stdout);
    int x,y,num;
    n=read(),m=read();
    for(int i=1;i<=m;++i)
        x=read()-1,y=read()-1,e[x][y]=e[y][x]=1,++du[x],++du[y];
    bin[0]=1;for(int i=1;i<=n;++i) bin[i]=bin[i-1]<<1;
    init(),Q=read();
    while(Q--) {
        num=read();int kl=0;
        for(int i=1;i<=num;++i) kl|=bin[read()-1];
        printf("%d\n",f[read()-1][kl]);
    }
    return 0;
}