AtCoder ARC #105 : F - Lights Out on Connected Graph

初手がわかれば後はすんなり。
https://atcoder.jp/contests/arc105/tasks/arc105_f

問題

N頂点M辺からなる連結単純無向グラフが与えられる。
このうち、一部の辺を残したグラフを考えよう。

以下の条件を満たす辺の残し方は2^M通りのうち何通りか。

• 連結である。
• 初期状態で辺が赤色の時、頂点を1つ選ぶとそこにつながる辺の色が赤と青で入れ替わるとする。任意個の頂点を選んだ時、全辺を青にできる。

解法

条件を考えると、各辺について両端のうちどちらか片方だけを選択することになるので、奇閉路がないこと、すなわち連結二部グラフであればよい。
ある辺の集合が条件を満たすとき、二部グラフは一通りに定まる。
そこで以下を考える。

f(S) := 頂点の部分集合Sとその誘導グラフにおいて、Sの各彩色方法(ただし1頂点は固定)におけるそのような二部グラフを達成する辺の組み合わせの総和
g(S) := ～～そのような連結二部グラフ～～

(Editorialには「2で割る」という作業があるが、今回は1頂点の色を固定したことで色の組み合わせが半減し、この作業は不要)
求めたいのは全頂点集合S'におけるf(S')であるが、直接求めるのは大変なのでg(S)から非連結な組み合わせを求めよう。

g(S)は以下のように求める。
彩色パターンを2^(|S|-1)通り総当たりしよう。そうするとその中で使える辺の数Pが決まるので、g(S)に2^Pを計上する。
g(S)が求められたら、f(S)=g(S)を初期値とし、そこから連結でないケースを引いていこう。
Sのうち1頂点を選びvとする。Sの部分集合のうち、Sより真に小さく、かつvを含むものTを総当たりする。
その場合f(S)からf(T)*g(S-T)を引こう。
このようにすることで、非連結なものを二重カウントすることなく引くことができる。

int N,M;
int E[17];
ll F[1<<17];
ll G[1<<17];
ll p2[500];

const ll mo=998244353;


void dfs(int cur,int F,int T,int sum) {
	if(cur==N) {
		G[F|T]+=p2[sum];
	}
	else {
		if(T&(1<<cur)) {
			dfs(cur+1,F,T,sum);
		}
		else {
			dfs(cur+1,F,T,sum);
			dfs(cur+1,F|(1<<cur),T,sum+__builtin_popcount(E[cur]&T));
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,499) p2[i+1]=p2[i]*2%mo;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x]|=1<<y;
		E[y]|=1<<x;
	}
	
	for(int mask=0;mask<1<<N;mask++) dfs(0,0,mask,0);
	
	F[0]=G[0]=1;
	for(int mask=1;mask<1<<N;mask++) {
		F[mask]=G[mask]=G[mask]%mo*((mo+1)/2)%mo;
		int msb=0;
		FOR(i,N) if(mask&(1<<i)) msb=1<<i;
		for(int sm=mask; sm&msb; sm=(sm-1)&mask) if(sm!=mask) F[mask]+=mo-F[sm]*2*G[mask^sm]%mo;
		F[mask]%=mo;
	}
	
	cout<<F[(1<<N)-1]<<endl;
	
	
	
}

まとめ

彩色ごとの辺を数え上げるのにbitcountを使ってもO(3^N*N)かかってしまってる…。