题目
思博状压写不出是不是没救了呀
首先我们直接状压当前最大独立集的大小显然是不对的，因为我们的答案还和我们考虑的顺序有关
我们发现最大独立集的个数好像不是很多，可能是\(O(n)\)级别的，于是我们考虑从这个方面入手
我们求出所有的最大独立集，考虑求出有多少种考虑顺序能够恰好得到这个最大独立集
设当前已经考虑的点的状态为\(S\)时的方案数为\(dp_S\)
我们考虑枚举出一个不在状态\(S\)的点\(x\)
分两种情况
\(x\)是最大独立集的点，所以我们可以把这个点加入\(S\)
\(x\)不是最大独立集的点，我们发现只有当和这个点相邻的且属于最大独立集的点加入\(S\)，我们才能加入\(x\)，这样\(x\)才能不被加入独立集
于是我们这样做就好啦，复杂度是\(O(2^nn^2)\)，卡卡常数就过去啦
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define lb(x) ((x)&(-x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=(1<<20)+5;
const int mod=998244353;
inline int read() {char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int st[maxn][21],top[maxn];
int cnt[maxn],f[maxn],vis[22],tot,ans,inv[22];
int n,m,N,d[22],g[maxn],dp[maxn],lg[maxn];
inline int chk(int S) {int t=S;while(t) {int x=lg[lb(t)];t-=lb(t);if(d[x]&S) return 0;}return 1;
}
inline void get(int S,int p) {int t=S;while(t) {int x=lg[lb(t)];t-=lb(t);st[p][++top[p]]=x;}
}
inline int qm(int a) {return a>=mod?a-mod:a;}
inline int calc(int S) {int t=S;memset(vis,0,sizeof(vis));while(t) {int x=lg[lb(t)];t-=lb(t);vis[x]=1;}memset(dp,0,sizeof(dp));dp[0]=1;for(re int i=0;i<N;i++) {for(re int j=1;j<=top[i];j++) {int x=st[i][j];if(vis[x]||(d[x]&S&i)) dp[i|(1<<(x-1))]=qm(dp[i|(1<<(x-1))]+dp[i]);}} return dp[N];
}
int main() {n=read(),m=read();N=(1<<n)-1;for(re int i=1;i<=N;i++) cnt[i]=cnt[i>>1]+(i&1);for(re int x,y,i=1;i<=m;i++) {x=read(),y=read();d[x]|=(1<<(y-1));d[y]|=(1<<(x-1));}for(re int i=1;i<=n;i++) lg[1<<(i-1)]=i;for(re int i=0;i<=N;i++) get(N^i,i);for(re int i=1;i<=N;i++) f[i]=chk(i);for(re int i=1;i<=N;i++) if(f[i]&&cnt[i]>cnt[ans]) ans=i;for(re int i=1;i<=N;i++) if(f[i]&&cnt[i]==cnt[ans]) tot=qm(tot+calc(i));inv[1]=1;for(re int i=2;i<=n;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;for(re int i=2;i<=n;i++) tot=(1ll*tot*inv[i])%mod;printf("%d\n",tot);return 0;
}至于\(O(2^nn)\)的正解好像很神仙的样子，大概是加入一个点的时候把和它相连的点都加入进来，转移的过程中还要乘上排列数，一看我就不会，于是就不写啦
