[LOJ2540] [PKUWC2018] 随机算法

题目链接

LOJ：https://loj.ac/problem/2540

Solution

写的时候脑子不太清醒码了好长然后时间\(LOJ\)垫底...

反正随便状压\(dp\)一下就好了，设\(f[i][s]\)表示当前用了\(i\)个点，最大独立集为\(s\)的方案数。

每次枚举下次放哪里就好了。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long

const int maxn = (1<<20)+10;

const int inf = 1e9;

const lf eps = 1e-8;

const int mod = 998244353;

int cnt[maxn],f[21][maxn],n,m,e[22][22],g[22][maxn],vis[21],h[maxn],inv[22];

int add(int x,int y) {return x+y>mod?x+y-mod:x+y;}

int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

int main() {

	read(n),read(m);for(int i=1,x,y;i<=m;i++) read(x),read(y),e[x][y]=e[y][x]=1;

	int all=1<<n;for(int i=1;i<all;i++) cnt[i]=cnt[i>>1]+(i&1);

	for(int s=0;s<all;s++) {

		memset(vis,0,sizeof vis);

		for(int i=1;i<=n;i++)

			if(s&(1<<(i-1))) {

				vis[i]=1;

				for(int j=1;j<=n;j++)

					if(e[i][j]) vis[j]=1;

			}

		for(int i=1;i<=n;i++) if(vis[i]) g[i][s]=1,h[s]++;

	}

	f[0][0]=1;

	for(int i=0;i<n;i++)

		for(int s=0;s<all;s++) {

			if(!f[i][s]) continue;

			for(int j=1;j<=n;j++)

				if(!g[j][s]) f[i+1][s|(1<<(j-1))]=add(f[i+1][s|(1<<(j-1))],f[i][s]);

			f[i+1][s]=add(f[i+1][s],mul(f[i][s],h[s]-i));

		}

	int res=0,ans=0;

	for(int s=0;s<all;s++) {

		int bo=1;

		for(int i=0;i<n;i++) if(s&(1<<i)&&g[i+1][s^(1<<i)]) bo=0;

		if(bo) res=max(res,cnt[s]);

	}

	for(int s=0;s<all;s++) if(cnt[s]==res) ans=add(ans,f[n][s]);

	inv[0]=inv[1]=1;

	for(int i=2;i<=n;i++) inv[i]=mul(mod-mod/i,inv[mod%i]),ans=mul(ans,inv[i]);

	write(ans);

	return 0;

}