场上数据很水，比较暴力的做法都可以过90分以上，下面说几个做法。
1. 暴力枚举所有最大独立集，对每个独立集分别DP。复杂度玄学，但是由于最大独立集并不多，所以可以拿90.
2. dp[S][k]表示考虑到排列的第k位，当前独立集为S的方案数，枚举第k+1位，根据是否与S相连转移到dp[S][k+1]或dp[S | a[k+1]][k+1]。$O(n^22^n)$
3. dp[S]表示排列的状态为S时的正确率，mx[S]表示排列状态为S时能得到的最大独立集大小，考虑转移，枚举排列里最后一个在独立集中的点i∈S，从S中删去所有与i相连的点得到S'，若mx[S]<mx[S']+1则更新mx[S]，dp[S]清零，否则累加。注意到每个排列都是等概率出现的，所以最后直接除以|S|即可。 $O(n2^n)$
方法一：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define ll long long
using namespace std; const int N=<<,mod=;
ll n,m,x,y,s[],p[],f[N][],cnt,mx,v[N],num[N],t[N],ans,o[N]; int main(){
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
scanf("%lld%lld",&n,&m);
p[]=; rep(i,,n) p[i]=p[i-]<<;
rep(i,,m) scanf("%lld%lld",&x,&y),s[x]|=p[y],s[y]|=p[x];
cnt=(<<n)-; f[][]=;
rep(i,,cnt){
ll tmp=; v[i]=;
rep(j,,n) if ((i&p[j])&&(s[j]&i)) v[i]=;
if (v[i]){
rep(j,,n) if (i&p[j]) tmp++,t[i]|=s[j];
num[i]=tmp; mx=max(mx,tmp);
tmp=;
rep(j,,n) if (t[i]&p[j]) tmp++;
o[i]=tmp;
}
}
rep(i,,cnt) if (v[i])
rep(j,,o[i]){
if (j!=o[i]) f[i][j+]=(f[i][j+]+f[i][j]*(o[i]-j))%mod;
rep(k,,n) if (!(i&p[k])&&!(p[k]&t[i])) f[i|p[k]][j]=(f[i|p[k]][j]+f[i][j])%mod;
if (num[i]==mx && j==o[i]) ans=(ans+f[i][j])%mod;
}
printf("%lld\n",ans);
return ;
}
方法二：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define P 998244353
#define N 21
#define t (1<<n)
int n,m;
long long ans=;
bool flag[<<(N-)];
int s[<<(N-)],w[N],v[<<(N-)],cnt[<<(N-)],tot[<<(N-)],f[][<<(N-)],maximum=;
int main()
{
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
n=read(),m=read();
for (int i=;i<=n;i++) w[i]=<<(i-),s[w[i]]=w[i];
for (int i=;i<=m;i++)
{
int x=read(),y=read();
s[w[x]]|=w[y],s[w[y]]|=w[x];
}
flag[]=;
for (int i=;i<t;i++)
if (flag[i])
for (int j=;j<=n;j++)
if (!(w[j]&s[i]))
{
flag[i|w[j]]=,s[i|w[j]]=s[i]|s[w[j]],cnt[i|w[j]]=cnt[i]+;
if (cnt[i]>=maximum) maximum=cnt[i|w[j]];
}
for (int i=;i<t;i++)
{
s[i]=(~s[i])&(t-);
register int k=s[i];
while (k) k^=k&-k,tot[i]++;
v[i]=i&-i;
}
f[][]=;
for (register int i=;i<n;i++)
for (register int j=;j<t;j++)
if (f[i][j])
{
for (register int k=s[j];k;k^=v[k])
f[i+][j|v[k]]=(f[i+][j|v[k]]+f[i][j])%P;
f[i+][j]=(1ll*f[i][j]*(n-i-tot[j])+f[i+][j])%P;
}
for (int i=;i<t;i++) if (cnt[i]==maximum) ans=(ans+f[n][i])%P;
cout<<ans;
fclose(stdin);fclose(stdout);
return ;
}
方法三：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=,mod=;
int n,m,x,y,inv[N],f[N],mx[<<N],F[<<N]; int main(){
scanf("%d%d",&n,&m);
rep(i,,m) scanf("%d%d",&x,&y),x--,y--,f[x]|=<<y,f[y]|=<<x;
inv[]=; f[]|=; F[]=;
rep(i,,n) f[i-]|=(<<(i-)),inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
for (int i=; i<(<<n); i++){
int tot=;
for (int j=; j<n; j++) if (i&(<<j)){
int s=i&(~f[j]);
if (mx[i]<mx[s]+) mx[i]=mx[s]+,F[i]=;
if (mx[i]==mx[s]+) F[i]=(F[i]+F[s])%mod;
tot++;
}
F[i]=1ll*F[i]*inv[tot]%mod;
}
printf("%d\n",F[(<<n)-]);
return ;
}