AtCoder ABC #213 : G - Connectivity 2

8問制になって難易度上がった？
https://atcoder.jp/contests/abc213/tasks/abc213_g

問題

N頂点M辺の無向グラフが与えられる。
このグラフからいくつかの辺を取り除く方法は2^M通りある。
その時、頂点1と頂点kが連結なのはそれぞれ何通りか。

解法

f(mask) := ビットマスクmaskに該当する頂点群が連結であるような辺の取り除き方の組み合わせ数
を全部求めれば、maskに頂点1,kが含まれるケースの総和を求めればよいことになる。

g(mask) := ビットマスクmaskに該当する頂点群における辺の取り除き方の組み合わせ数
とすると、これはmaskに含まれる辺の数mに対しg(mask)=2^mと容易に計算できる。

f(mask)は、g(mask)から明らかに連結でないケースを引けばよい。
maskに含まれるある頂点vを1つ選ぶと、smをmaskの部分集合となるビットマスクのうちvを含むものとすると、
f(mask) = g(mask) - sum(f(sm)*g(mask^sm))
で求めることができる。これはO(3^N)で処理できる。

int N,M;
int E[17][17];
ll G[1<<17];
ll F[1<<17];
const ll mo=998244353;


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

まとめ

このパターンの数え上げはしばしば見るね。