TopCoder12004 SetAndSet

题意：给定 $n$ 个数，要求把他们分成红蓝两组，要求都不为空，使得红组的 AND 和蓝组的 AND 相同，求划分方案。$n\leq 50, a < 2 ^ {20}$。

容易发现不管怎么 DP 都是至少 $O(a ^ 2n)$ 的，不可接受。

考虑朴素容斥，假设某一位不相同，那么所有该位为 1 的数都应该在同一组，容斥这一位不相同，那么将所有该位为 1 的数同并查集合并，然后最后看有几组，答案就是 $2 ^ {cnt} - 2$。

注意如果一个位置一个该位为 1 的数都没有，那么不能对该位进行容斥。用个 dfs 搜一搜即可。复杂度 $O(na)$。

class SetAndSet {
private:
	int n;
	std::vector<int> f;
	std::vector<int> all[20];
	LL res;
	
	int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
	bool merge(int u, int v)
	{
		if (find(u) == find(v)) return false;
		return f[find(v)] = find(u), true;
	}
	
	void dfs(int bit, int op)
	{
		if (bit == 20) {
			int cnt = 0;
			for (int i = 0; i < n; ++ i) cnt += f[i] == i;
			res += op * ((1LL << cnt) - 2);
			return;
		}
		dfs(bit + 1, op);
		if (all[bit].size()) {
			auto bac = f;
			for (int i = 1; i < (int) all[bit].size(); ++ i)
				merge(all[bit][i], all[bit][0]);
			dfs(bit + 1, -op);
			f = bac;
		}
	}
	
public:
	LL countandset(std::vector<int> a)
	{
		n = a.size(), res = 0;
		f.resize(n);
		for (int i = 0; i < n; ++ i) f[i] = i;
		for (int bit = 0; bit < 20; ++ bit)
			for (int i = 0; i < n; ++ i)
				if (!(a[i] >> bit & 1)) all[bit].push_back(i);
		return dfs(0, 1), res;
	}
};