TopCoder SRM 545 Div1 Hard SetAndSet

問題

Aを非負の整数列とする。
Aの各要素を赤または青に色づけする。

色づけ後で、それぞれの色に色づけされた要素のAND（ビット毎のand）を
取ったとき、両者が等しくなっているような色づけの仕方は何通りあるか、求めよ。

制約条件

A[i]≦1048575
Aの要素≦50

方針

包除原理で計算する。

各ビットごとに見たとき、
全てのiでビットが0または1であるビットは無視してよい。
0と1が混在するビットは、0が全て同じ色になると、条件を満たさなくなる。

ここで、見るビットの集合Tを決めたときにTの全てで失敗する場合の数をg(T)と置くと、
g(T)を全部計算し、包除原理を使うことで、
ある集合Sに対してどこか一つで失敗する場合の数f(S)が求まる。

g(T)は再帰とunion-findを使いながら求めていく。
あるビットをTに加えるとき、0が二つ立っているビットがあったら、それらの色は同じにしなくてはならないので、その要素同士をマージする。
というのを繰り返した後、
2 ^ (連結成分の個数 + n - 0が登場しなかった要素)
というのがg(T)になっている。

union-findは再帰のたびに前のものを保存して、再帰が終わったら復元する。

ソースコード

bool v[60];
int n, m, p[30][60];
ll nz[60], ans;

void rec(int cur, int use, int k, ll paint){
	if(cur == m){
		ll tmp = 1ll << k + n - __builtin_popcountll(paint);
		if(use % 2) ans -= tmp;
		else ans += tmp;
	}
	else{
		v[cur] = 1;
		int nk = k + 1;
		
		rep(i, cur) p[cur][i] = p[cur - 1][i];
		p[cur][cur] = cur;
		
		for(int i = cur - 1; i >= 0; i--){
			if(v[i] && (nz[cur] & nz[i])){
				if(p[cur][p[cur][i]] != cur)
				p[cur][p[cur][i]] = cur, nk--;
			}
		}
		for(int i = cur - 1; i >= 0; i--){
			p[cur][i] = p[cur][p[cur][i]];
		}
		rec(cur + 1, use + 1, nk, paint | nz[cur]);
		
		rep(i, cur) p[cur][i] = p[cur - 1][i];
		p[cur][cur] = cur;
		v[cur] = 0;
		rec(cur + 1, use, k, paint);
	}
}

class SetAndSet {
	public:
	long long countandset(vector <int> A) 
	{
		n = A.size();
		m = 0;
		rep(j, 20){
			ll bit = 0;
			rep(i, n) if(!(A[i] >> j & 1)) bit |= 1ll << i;
			if(bit != (1ll << n) - 1 && bit) nz[m++] = bit;
		}
		if(m == 0) return (1ll << n) - 2;
		ans = 0;
		memset(v, 0, sizeof(v));
		rec(0, 0, 0, 0);
		return ans;
	}
};