给你一个$n$个点$m$条边的无向图，执行如下算法：
1.随机一个$1~n$的排列$P$
2.从$P$中按顺序一个一个将点加进独立集$S$里，始终保证$S$是独立集（即如果当前点和当前集合里的某个点相邻，就不加了）
求最后得到的$S$是原图的一个最大独立集的概率
$50 n leq 17$
$100 n leq 20$
sol：
先考虑部分分吧
很暴力的状压dp，$F[S1][S2]$表示选了$S1$中的点，当前最大独立集是$S2$的方案数，最后除以$n!$就可以了
转移是枚举每个点，所以复杂度是$O(n3^n)$的（$S2$一定是$S1$的子集）
后面的做法有点神仙
我不会做啊QAQ
观察题面，我们可以把点分为“考虑过的”和“现在还没考虑到的”
我们用$F_{(S,i)}$表示考虑了$S$集合，当前最大独立集为$i$的方案数其实可以优化，因为我们发现对于一个集合$S$，它的最大独立集是确定的，我们可以用$g[S]$来记录它，这是状态就可以优化一维
转移的时候，枚举一下第一个加到独立集里的点$i$，删去$i$和与$i$相邻的点，用它更新$g[S]$，再更新一下$F_S$即可
根本不可做呀
嘤嘤嘤
#include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = (1 << 20) + 10,mod = 998244353; int n,m; int a[21]; int dp[maxn],mx[maxn]; int fac[30],ifac[30]; inline int ksm(int x,int t) { int res = 1; while(t) { if(t & 1)res = res * x % mod; x = x * x % mod; t = t >> 1; } return res; } inline int A(int n,int m) { return fac[n] * ifac[n - m] % mod; } signed main() { n = read(),m = read(); for(int i=1;i<=m;i++) { int u = read() - 1,v = read() - 1; a[u] |= (1 << (v)); a[v] |= (1 << (u)); }int MAXSTATE = (1 << n) - 1; fac[0] = 1,ifac[0] = 1;ifac[1] = 1; for(int i=1;i<=29;i++)fac[i] = (fac[i - 1] * i) % mod,ifac[i] = ksm(fac[i],mod - 2); //for(int i=1;i<=20;i++)cout<<fac[i]<<" "<<ifac[i]<<endl; //for(int i=0;i<=n;i++)a[i] |= i; dp[0] = 1; for(int s=0;s<=MAXSTATE;s++) if(dp[s]) { for(int i=0;i<n;i++) if (!(s>>i&1)) { int t = s | a[i] | (1 << i); if(mx[t] < mx[s] + 1)mx[t] = mx[s] + 1, dp[t] = 0; if(mx[t] == mx[s] + 1) dp[t] = (dp[t] + dp[s] * A(n - __builtin_popcount(s) - 1,__builtin_popcount(a[i]) - __builtin_popcount(a[i] & s))) % mod; } } cout<<dp[MAXSTATE] * ifac[n] % mod; }