大致题意： 用随机算法求一张图的最大独立集：每次随机一个排列，从前到后枚举排列中的点，如果当前点加入点集中依然是独立集，就将当前点加入点集中，最终得到的点集就是最大独立集。求这个随机算法的正确率。
前言
(PKUWC)的题目就是妙啊。
题目很神仙，但看完题解后就很简单了，可这种东西像我这般蒟蒻根本想不到啊......
状压(DP)
设(f_{i,j})表示当前已考虑过点集(i)，最大独立集为(j)的方案数。
每次我们枚举一个不在点集中的点(k)，设与其相邻的点的集合为(a_k)。
则，如果我们要选择点(k)作为独立集中的点，那么与其相邻的点就不能再选择，方便起见，我们直接把(a_k)算作考虑过的点。
即，对于(f_{i,j})和(k)，我们可以转移到(f_{i|2^{k-1}|a_k,j+1})。
注，这里之所以是(2^{k-1})，因为我习惯用二进制下第(x-1)位来表示第(x)个数是否被选择。
不难发现，根据我们的转移方式，由于(k)不在点集中，所以点集中被选作独立集中的点的点一定不与(k)相邻，否则在那个点被选作独立集中的点时就已经把(k)加入点集了，因此必然(j)可以加(1)。
然后我们考虑，在这一步转移下，(k)肯定是要直接加入点集中的，即必然在剩下的点中名列第一，它的位置是固定的。
而对于那些与(k)相邻、又不在点集(i)中的点（即：(a_k-(i&a_k))），它们可以在(k)之后的任意一个位置（共有(n-g_i-1)个位置，其中(g_i)代表点集(i)中的点，(1)代表点(k)）加入点集，因此方案数为(A_{n-g_i-1}^{g_{a_k-(i& a_k)}})。
其中，(A)表示排列数，(A_n^m=frac{n!}{(n-m)!})；(g_i)表示点集(i)中点的个数。
所以：(f_{i|2^{k-1}|a_k,j+1}+=f_{i,j}cdot A_{n-g_i-1}^{g_{a_k-(i&a_k)}})。
由于求概率，而我们求的是方案数，所以最后的答案就是：(frac{f_{2^n-1,w}}{n!})，其中(w)表示最大独立集的大小。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 20
#define X 998244353
#define A(x,y) (1LL*Fac[x]*IFac[(x)-(y)]%X)
using namespace std;
int n,m,a[N+5],f[1<<N][N+5],g[1<<N],Fac[N+5],IFac[N+5];
I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
RI i,x,y;for(scanf("%d%d",&n,&m),i=1;i<=m;++i) scanf("%d%d",&x,&y),a[x]|=1<<y-1,a[y]|=1<<x-1;//读入，记录相邻点
for(Fac[0]=i=1;i<=N;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[N]=Qpow(Fac[N],X-2),i=N-1;~i;--i) IFac[i]=1LL*IFac[i+1]*(i+1)%X;//预处理阶乘逆元
RI j,k,t=1<<n;for(i=0;i^t;++i) g[i]=g[i>>1]+(i&1);for(f[0][0]=1,i=0;i^t;++i)//枚举点集
{
for(j=0;j<=g[i];++j) for(k=1;k<=n;++k) !((i>>k-1)&1)&&//一定要选择不在点集中的点
(f[i|(1<<k-1)|a[k]][j+1]=(1LL*f[i][j]*A(n-g[i]-1,g[a[k]-(i&a[k])])+f[i|(1<<k-1)|a[k]][j+1])%X);//转移
}
for(i=n;!f[t-1][i];--i);return printf("%d",1LL*f[t-1][i]*IFac[n]%X),0;//求最大独立集点数，然后输出答案
}