loj#2540. 「PKUWC2018」随机算法

题目
思路
$f[S]$表示已经覆盖了$S$的状态的最大独立集大小
$g[S]$表示此时的算法正确的方案数（最后除以$n!$就是期望了）
设新加入的扩充最大独立集的点为$i$，与i相连的点的状态为$t{o}_i$，那么
$g[S|t{o}_i]=\sum g[S]\cdot A_{n-|S|-1}^{|t{o}_i-S|-1}$（集合的减这里表示差集，因为“”$markdown$里输不进QAQ）
排列的意义：已经选了$i$这个点，那么与$i$相连的点也要覆盖掉，这些点按题目中的算法随意排列都是正确的

#include<cstdio>
const int N=1<<20,M=998244353;
int n,m,i,x,y,to[N],f[N],g[N],s,v,F[21],G[21],cnt[N];
#define A(n,m) (1ll*F[n]*G[(n)-(m)]%M)
int main(){
	scanf("%d%d",&n,&m);
	for (;m--;) scanf("%d%d",&x,&y),x--,y--,to[x]|=1<<y,to[y]|=1<<x;
	F[0]=G[0]=F[1]=G[1]=1;
	for (i=2;i<=n;i++) F[i]=1ll*F[i-1]*i%M,G[i]=1ll*(M-M/i)*G[M%i]%M;
	for (i=1;i<=n;i++) G[i]=1ll*G[i]*G[i-1]%M;
	for (i=0;i<n;i++) to[i]|=1<<i;
	for (s=0;s<1<<n;s++) cnt[s]=cnt[s>>1]+(s&1);
	g[0]=1;
	for (s=0;s<1<<n;s++) if (g[s]){
		for (i=0;i<n;i++) if (!(s&(1<<i))){
			v=s|to[i];
			if (f[v]<f[s]+1) f[v]=f[s]+1,g[v]=0;
			if (f[v]==f[s]+1) g[v]=(g[v]+1ll*g[s]*A(n-cnt[s]-1,cnt[v^s]-1))%M;
		}
	}
	printf("%lld",1ll*g[(1<<n)-1]*G[n]%M);
}

最后

以上就是勤劳月饼为你收集整理的loj#2540. 「PKUWC2018」随机算法的全部内容，希望文章能够帮你解决loj#2540. 「PKUWC2018」随机算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。