TopCoder SRM 691 Div1 Easy Sunnygraphs

最近Div1 Easy難しくない？
https://community.topcoder.com/stat?c=problem_statement&pm=14291

問題

0～(N-1)番のN頂点のグラフがある。
i番の頂点はA[i]番の頂点と無向辺で結ばれている(同じ頂点対に２つの辺が張られることもある)。
N頂点の部分集合Mに対し、v∈Mである各vについて、vとA[v]の辺を消し、代わりにvとN番の間に辺をつなぐ。

Mの選び方2^N通りに対し、0番と1番が連結する組み合わせ数を求めよ。

解法

まず0番とも1番とも連結しない辺の挙動は関係ないので、それらの挙動は気にしなくてよい。
よってそのような頂点がa個あるなら、他の頂点に組み合わせに対し2^aを掛け合わせよう。

あとは0,1番と連結する頂点のみを考える。
問題文は無向辺だが、有向辺として考えよう。

元々0番と1番が連結しない場合、0番または1番から到達可能な頂点のうち、それぞれ最低1辺がN番とつながれば条件を満たす。
よってそれぞれの頂点数をb,cとすると(2^a)*(2^b-1)*(2^c-1)が解。

0番と1番が連結する場合、0番からのみ到達可能な頂点と、1番からのみ到達可能な頂点のうち、片方だけにN番とつながる辺があり、かつ両方からつながる頂点からN番につながる辺がないと条件を満たせない。
そうでない場合、両者からつながる頂点はどちらでも良い。
よって0,1番からのみ到達可能な頂点数をb,c、両方から到達可能な頂点数をdとすると、(2^a)*(((2^b-1)*(2^c-1)+1)*2^d)+*1*(2^d-1))。

class Sunnygraphs {
	public:
	int mat[60][60];
	
	long long count(vector <int> a) {
		int N=a.size();
		int i,x,y,z;
		ZERO(mat);
		
		FOR(x,N) FOR(y,N) mat[x][y]=1010;
		FOR(i,N) mat[i][a[i]]=1, mat[i][i]=0;
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y] = min(mat[x][y],mat[x][z]+mat[z][y]);
		
		ll m0=0,m1=0;
		FOR(i,N) if(mat[0][i]<1000) m0 |= 1LL<<i;
		FOR(i,N) if(mat[1][i]<1000) m1 |= 1LL<<i;
		int only0 = __builtin_popcountll(m0 ^ (m0&m1));
		int only1 = __builtin_popcountll(m1 ^ (m0&m1));
		int both = __builtin_popcountll(m0&m1);
		int nor = N-(both+only0+only1);
		
		if(both==0) return (1LL<<nor)*((1LL<<only0)-1)*((1LL<<only1)-1);
		return (1LL<<nor)*(((((1LL<<only0)-1)*((1LL<<only1)-1)+1)<<both)+(((1LL<<only0)-1)+((1LL<<only1)-1))*((1LL<<both)-1));
		
	}
}

まとめ

Div2 Mediumもちょっと考える問題だったしね。

*1:2^b-1)+(2^c-1