Codeforces ECR #073 : G. Graph And Numbers

言われてみると簡単なんだけどね。
https://codeforces.com/contest/1221/problem/G

問題

N頂点M辺からなる無向グラフが与えられる。
各頂点に0,1の値を振ることを考えるその振り方は2^N通りある。
ここで、各辺に両端点の値の和を書くことにする。
その時、0,1,2がそれぞれ最低1回ずつは登場するような振り方は何通りか。

解法

包除原理で解く。
f(S) := S内の値が辺の値として登場することを許容するような組み合わせの数
とすると、解はf({0,1,2})-f({0,1})-f({0,2})-f({1,2})-f({0})-f({1})-f({2})となる。
ここで、辺の値を01反転することを考えるとf({0,1})=f({1,2})、f({0})=f({2})となる。
以下それぞれ考えよう。

• f({0,1,2}) : 各点何を振ってもいいので2^N通り
• f({0}), f({2}), f({0,2}) : 辺を持たない連結成分は01何を振ってもよく、辺を持つ連結成分はそれぞれ0,1固定。
• f({1}) : 辺を持たない連結成分は01何を振ってもよい。辺を持つ連結成分はそれぞれ2部グラフを構築しなければならず、それぞれ2通り。
• f({0,1}), f({1,2}) : これが一番面倒。半分全列挙で、前半N/2頂点の0,1の組み合わせと後半の0,1の組み合わせで、高速ゼータ変換を行いながら、前半と後半の間で1を振った点が結ばれないものを数え上げる。

int N,M;
ll E[51];
template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<41> uf;
int vis[51];
ll num[1<<20];

ll F012() {
	return 1LL<<N;
}

ll F01() {
	int i;
	int mask;
	ll ret=0;
	FOR(mask,1<<(min(20,N))) {
		int ok=1;
		FOR(i,min(20,N)) if(mask&(1<<i)) {
			if(E[i]&mask) ok=0;
		}
		num[mask]=ok;
	}
	FOR(i,20) FOR(mask,1<<20) if(mask&(1<<i)) num[mask]+=num[mask^(1<<i)];
	FOR(mask,1<<20) {
		int ok=1;
		ll tmask=0;
		FOR(i,20) if(mask&(1<<i)) {
			if(i+20>=N) ok=0;
			tmask |= E[i+20];
			if(mask&(E[i+20]>>20)) ok=0;
		}
		if(ok) {
			tmask = ~tmask&((1<<20)-1);
			ret+=num[tmask];
		}
	}
	return ret;
}


ll F02(){
	int C=0;
	int i;
	FOR(i,N) if(uf[i]==i) C++;
	return 1LL<<C;
}
ll F0() {
	int C=0;
	int i;
	FOR(i,N) if(E[i]==0) C++;
	return 1LL<<C;
}

int dfs(int cur,int pre,int v) {
	if(vis[cur]!=-1) return vis[cur]==v;
	vis[cur]=v;
	int ret=1;
	int i;
	FOR(i,N) if(E[cur]&(1LL<<i)) ret &= dfs(i,cur,v^1);
	return ret;
}
ll F1() {
	ll ret=1;
	int i;
	MINUS(vis);
	FOR(i,N) if(uf[i]==i) {
		if(dfs(i,-1,0)==0) return 0;
		ret*=2;
	}
	return ret;
}
ll F() {
	if(M==0) return 1LL<<N;
	return 0;
}
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		uf(x,y);
		E[x] |= 1LL<<y;
		E[y] |= 1LL<<x;
	}
	
	ll ret=F012()-2*F01()-F02()+2*F0()+F1()-F();
	cout<<ret<<endl;
}

まとめ

言われればわかるけど細かいところが割と面倒な問題。