又是一道被咕了很久的题 貌似从WC2019之前咕到了现在
我们用f[i][s]表示现在最大独立集的大小为i 不可选集合为s
然后转移O(n)枚举加进来的点就比较简单啦
这个的复杂度是O(2^n*n^2)
据说有更科学的O(2^n*n)
但是显然这个做法就能过了（
详情参见PKUWC2019D1T1（大雾
代码扔这里了。
//Love and Freedom. #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> #define ll long long #define inf 20021225 #define mdn 998244353 #define N 21 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } int ksm(int bs,int mi) { int ans=1; while(mi) { if(mi&1) ans=1ll*ans*bs%mdn; bs=1ll*bs*bs%mdn; mi>>=1; } return ans; } int f[N][1<<N],fac[N],inv[N],cnt[1<<N],n,w[N]; void add(int x,int y) { w[x]|=1<<y; w[y]|=1<<x; } int A(int n,int m) { if(n<m) return 0; return 1ll*fac[n]*inv[n-m]%mdn; } void upd(int &x,int y){x+=x+y>=mdn?y-mdn:y;} int main() { n=read(); int m=read(); fac[0]=1; int x,y; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mdn; inv[n]=ksm(fac[n],mdn-2); for(int i=n;i;i--) inv[i-1]=1ll*inv[i]*i%mdn; for(int i=1;i<=m;i++) x=read(),y=read(),add(x-1,y-1); for(int i=0;i<n;i++) w[i]|=1<<i; f[0][0]=1; int top=1<<n; for(int i=1;i<top;i++) cnt[i]=cnt[i>>1]+(i&1); for(int i=0;i<n;i++) for(int s=0;s<top;s++) if(f[i][s]) for(int j=0;j<n;j++) if(!((s>>j)&1)) upd(f[i+1][s|w[j]],1ll*f[i][s]*A(n-cnt[s]-1,cnt[w[j]-(w[j]&s)]-1)%mdn); for(int i=n;i;i--) if(f[i][top-1]) { printf("%d ",1ll*f[i][top-1]*inv[n]%mdn); break; } return 0; }