题意
给定一无向图，每条边等概率正向、反向、消失，求其成为 DAG 的概率。\(n\leq 20\)。
题解
先算方案数，再算期望。
设 \(E(S)\) 为点集 \(S\) 的导出子图的边集大小。枚举入度为 \(0\) 的点集，得到转移：
\[F(S)=\sum_{T\subseteq S,T\neq \varnothing}(-1)^{|T|-1}2^{E(S)-E(T)-E(S-T)}F(S-T) \] \[\dfrac{F(S)}{2^{E(S)}}=\sum_{T\subseteq S,T\neq \varnothing}\dfrac{(-1)^{|T|-1}}{2^{E(T)}}\dfrac{F(S-T)}{2^{E(S-T)}} \]子集卷积。
#include<bits/stdc++.h>
using namespace std;
const int N=21,mod=998244353,inv2=(mod+1)/2;
int f[N][1<<N],g[N][1<<N];
int popc[1<<N],e[1<<N];
int p2[N*N];
int b[N];
int n,m;
int p[1<<N];
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1)ans=ans*1ll*x%mod;
x=x*1ll*x%mod;
y>>=1;
}
return ans;
}
void fwt(int *a,int m,int tp){
for(int i=1;i<1<<m;i<<=1){
for(int j=0;j<1<<m;j+=i<<1){
for(int k=0;k<i;k++){
int x=a[j+k],y=a[i+j+k];
// cerr<<". "<<j+k<<" "<<i+j+k<<endl;
a[j+k]=x+y;a[i+j+k]=x-y;
a[j+k]>=mod&&(a[j+k]-=mod);
a[i+j+k]<0&&(a[i+j+k]+=mod);
}
}
}
if(tp==-1){
int q=qpow(1<<m,mod-2);
for(int i=0;i<1<<m;i++)
a[i]=a[i]*1ll*q%mod;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
--u,--v;
b[u]|=1<<v;
b[v]|=1<<u;
}
p2[0]=1;for(int i=1;i<=n*n;i++)p2[i]=p2[i-1]*1ll*inv2%mod;
// g[0][0]=1;
for(int i=1;i<1<<n;i++){
int k=i^(i&-i);
int t=0;while((i&-i)>>t)++t;--t;
popc[i]=popc[k]+1;
e[i]=e[k]+popc[b[t]&k];
g[popc[i]][i]=(popc[i]&1)?p2[e[i]]:mod-p2[e[i]];
}
for(int i=0;i<=n;i++)fwt(g[i],n,1);
f[0][0]=1;
fwt(f[0],n,1);
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
for(int k=0;k<1<<n;k++)
f[i][k]=(f[i][k]+f[j][k]*1ll*g[i-j][k])%mod;
}
}
fwt(f[n],n,-1);
cout<<f[n][(1<<n)-1]*1ll*qpow((mod+1)/3*2,m)%mod;
}