Codeforces #257 Div1 D. Jzzhu and Numbers

知っていればコードはあっさり。
http://codeforces.com/contest/449/problem/D

問題

K要素の数列A[i](<=M)が与えられる。
この数列から1個以上の要素をもつ部分列のうち、部分列中の全要素のandが0となるものの数を答えよ。

解法

Editorialよりも、コンテスト開催のblog記事のコメントの方がわかりやすい。

全要素のandがxとなるようなA[i]の部分集合をS[x]とする。
A[i] & x == xとなるA[i]の数をP[x]個とすると、S[x]の選び方は2^P[x]通りである。

P[x]がわかればS[x]がわかり、後は包除原理の要領でS[0]を求めればよい。
P[x]の求め方は、一見O(K*M)かかりそうだが、bitごとの畳み込みを使うとO(K*logM)で処理できる。
巷では高速ゼータ変換とか呼ばれているようだ。

ll N,A[1<<21],P2[1<<21];
ll mo=1000000007;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>x, A[x]++;
	P2[0]=1;
	FOR(i,1<<20) P2[i+1]=P2[i]*2%mo;
	FOR(i,20) FOR(x,1<<20) if((x&(1<<i))==0) A[x]+=A[x|(1<<i)];
	ll ret=0;
	FOR(i,1<<20) {
		if(__builtin_popcount(i)%2) ret-=P2[A[i]]%mo;
		else ret+=P2[A[i]]%mo;
	}
	ret=((ret%mo)+mo)%mo;
	cout << ret << endl;
}

まとめ

コードは単純だが、包除原理が苦手なうえに高速ゼータ変換相当の処理が思い浮かばなかった。
#258でも包除原理落としたし、ちゃんと理解しないとなぁ。