Codeforces #225(383 Div1) E. Vowels

問題

英小文字のうちa-xの24文字のどれか、3文字からなる単語がn個与えられる。
24文字のうち好きな文字を母音にしてよい。

母音が一文字以上含まれている単語はよい単語である。
2^24の母音の選び方に対して、(良い単語の数)^2を求め、それらを全てxorしたものを出力せよ。

制約条件

n≦10000

方針

こどふぉ史上最も酷いE？ゼータ変換するだけ。
ある単語のもつ文字の集合をbitで表す。

この単語をダメにする母音の選び方の集合は、~bitの部分集合。
なので、~bitの部分集合全てに1を足したい感じ。
これは部分集合に個数を伝播させるゼータ変換をすればいい。

そしたら、全てのbitについて、ダメな単語の個数がわかるので、nから引いて二乗すればよい。

ソースコード

int n, a[1 << 24];

int main(){
	scanf("%d", &n);
	rep(i, n){
		char buf[5]; scanf("%s", buf);
		int bit = (1 << 24) - 1;
		rep(j, 3) bit &= ~(1 << buf[j] - 'a');
		a[bit]++;
	}
	rep (i, 24) rep(b, 1 << 24) if (!(b & 1 << i)) a[b] += a[b | (1 << i)];
	
	ll ans = 0;
	rep(i, 1 << 24) ans ^= (ll)(n - a[i]) * (n - a[i]);
	cout << ans << endl;
	
	return 0;
}