「PKUWC 2018」随机算法 (第二版，正解做法)

上一版貌似是打了 O(3 ^ N) 暴力和一条链的情况，得了60分。。。。

第一次做的时候光想练一练暴力。。。就没去想正解，谁知道正解比暴力好写不知道多少,mmp

设 f(S) 为选集合S中的点可以得最大独立集的概率， M(S) 为集合S 中的点构成的最大独立集是多少。

那么我们转移的时候，就枚举一下集合S中第一个加入独立集的点i，删去集合中和i相邻的点(包括i)，得到s'，用它更新M()之后，f()就可以顺带算出来了。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int ha=998244353,maxn=2333333;

inline void add(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

int p[29],n,m,ci[33],f[maxn],M[maxn],inv[33],all;

int main(){

	ci[0]=inv[1]=1,ci[1]=2;

	for(int i=2;i<=30;i++) ci[i]=ci[i-1]<<1,inv[i]=ha-inv[ha%i]*(ll)(ha/i)%ha;

	scanf("%d%d",&n,&m),all=ci[n]-1;

	int uu,vv;

	while(m--) scanf("%d%d",&uu,&vv),uu--,vv--,p[uu]|=ci[vv],p[vv]|=ci[uu];

	for(int i=0;i<n;i++) p[i]|=ci[i];

	f[0]=1,M[0]=0;

	for(int i=1,now;i<=all;i++){

		now=0;

	    for(int j=0,lef;j<n;j++) if(ci[j]&i){

	    	lef=(all^p[j])&i,now++;

	    	if(M[lef]>=M[i]) M[i]=M[lef]+1,f[i]=f[lef];

	    	else if(M[lef]+1==M[i]) add(f[i],f[lef]);

		}

		f[i]=f[i]*(ll)inv[now]%ha;

	}

	printf("%d\n",f[all]);

	return 0;

}

巴特西

「PKUWC 2018」随机算法 (第二版，正解做法)

最新文章

热门文章