RT

状压 DP + 容斥原理。

蛙的惨状

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=18;
const int M=N*N;
const int mod=998244353;
int n,m,u[M],v[M];
int g[1<<N],p[1<<N],f[1<<N];
int popcount(int x){
	int res=0;
	while(x) x&=(x-1),res++;
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&u[i],&v[i]),u[i]--,v[i]--;
	for(int se=1;se<(1<<n);se++){
		g[se]=1,p[se]=popcount(se);
		for(int j=1;j<=m;j++){
			if(((se>>u[j])&1)&&((se>>v[j])&1)) g[se]=0;
		}
	}
	f[0]=1;
	for(int se=1;se<(1<<n);se++){
		for(int es=se;es;es=(es-1)&se){
			if(g[es]) f[se]=(f[se]+f[se^es]*(es&1?1:-1))%mod;
		}
	}
	printf("%d",(long long)(f[(1<<n)-1]+mod)*m%mod*499122177%mod);
	return 0;
}