TopCoderOpen 2016 Round2A Medium CliqueCuts

これは自力はちょっときついな。
https://community.topcoder.com/stat?c=problem_statement&pm=14176

問題

N頂点からなる無向グラフが与えられる。
各頂点はスコアが振られている。

グラフのうち、正の頂点数からなるクリークを１つ選ぶ事を考える。
このクリークに属する頂点群を赤、それ以外を青で塗ろう。
この時のグラフのスコアは、両端が赤頂点の辺のスコアの和から、両端が青頂点の辺のスコアの和を引いたものに等しい。

クリークの選び方全通りに対し、スコアの総和を求めよ。

解法

Editorialを見て解いた。

まず辺のスコアの和を考えるのは面倒なので、頂点のスコアを考えよう。
各頂点の色を定めたとき、赤頂点に接続する点の総スコアから青頂点に接続する点の総スコアを引くと、グラフのスコアの倍になる。
こう考えると、結局各頂点が赤・青になる組み合わせ数を列挙すればよいことになる。

あとは半分全列挙で解く。
まず半分の頂点に対し、頂点群の選択をbitmaskで総当たりし、クリークを成すかどうか判定しよう。
クリークを成す場合、その半分の頂点に対するスコアを求める。

次に、高速ゼータ変換の要領で、各bitmaskに対し、そのbitmaskの部分maskに対するクリーク数及びスコアの総和を求めよう。
この手順を行った後、bitmask内のクリーク数をC(mask)、総スコアをS(mask)としよう。

次に残り半分をbitmaskで総当たりする。
ある頂点群mask2がクリークを成す場合、それらの頂点のスコアの総和をS2(mask2)とする。
それらすべての頂点と接続される前半の半分の頂点群のbitmaskをmask3としたとき、C(mask3)*S2(mask2) + S(mask3)を答えに加算すればよい。

なお、上記解法は１つも頂点を選ばない状態を含んでいるので、そのような状態のスコアを取り除いた上で２で割ったものが解。

ll mat[51];
ll sc[51];

ll npat[1<<23];
ll tot[1<<23];
ll mo=1000000007;

class CliqueCuts {
	public:
	int sum(int n, vector <int> a, vector <int> b, vector <int> c) {
		ZERO(mat);
		ZERO(sc);
		
		int h=n/2,le=n-h;
		int i,x,y;
		ll mask;
		FOR(i,n) mat[i] |= 1LL<<i;
		FOR(i,a.size()) {
			mat[a[i]] |= 1LL<<b[i];
			mat[b[i]] |= 1LL<<a[i];
			sc[a[i]]+=c[i];
			sc[b[i]]+=c[i];
		}
		
		FOR(mask,1<<h) {
			int ok=1;
			ll to=0;
			FOR(i,h) {
				if(mask & (1<<i)) {
					if((mask & mat[i])!=mask) ok=0;
					to += sc[i];
				}
				else to -= sc[i];
			}
			if(ok) {
				tot[mask] = ((to%mo)+mo)%mo;
				npat[mask] = 1;
			}
			else {
				tot[mask]=npat[mask]=0;
			}
		}
		
		FOR(i,h) FOR(mask,1<<h) if(mask&(1<<i)) {
			npat[mask] = (npat[mask]+npat[mask^(1<<i)])%mo;
			tot[mask] = (tot[mask]+tot[mask^(1<<i)])%mo;
		}
		
		ll ret=0;
		for(mask=0;mask<1LL<<n;mask += 1LL<<h) {
			int ok=1;
			ll tmask = (1<<h)-1;
			ll to=0;
			for(i=h;i<n;i++) {
				if(mask & (1LL<<i)) {
					if((mask & mat[i])!=mask) ok=0;
					to += sc[i];
					tmask &= mat[i];
				}
				else to -= sc[i];
			}
			if(ok) ret += (((to%mo)+mo)%mo)*npat[tmask] % mo + tot[tmask];
		}
		
		FOR(i,n) ret += sc[i];
		return (ret%mo+mo)%mo * ((mo+1)/2) % mo;
		
	}
}

まとめ

言われてみればそうなんだけど、自力で思いつく気がしない。