CSAcademy Round #13 : E. And Closure

これは思いつけて良かった。
https://csacademy.com/contest/round-13/#task/and-closure

問題

整数の集合Sがある。
これらの部分集合を取り、すべてのbitwise-andを取ってできる数は何通りか。

解法

ある数xを作りたいとする。
その場合Sからbitwiseでxを含むような数を全て選んでみて、そのbitwise-orがxに一致すればよい。
この処理を高速ゼータ変換で高速化しよう。

以下の値A(x)を考える。
A(x):= bitwiseでxを含むような数を全て選んだとき、0となるbitをsetしたもの

入力値にpがあったら、A(p) = ~pとする。
その上で高速ゼータ変換で重ね合わせていく。
あとはxを0～10^6で総当たりし、A(x) = ~xとなる数を求める。
なお、1つも選択しない場合は0が生成できるので、そこだけ二重カウントしないように注意。

int N;
int A[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int can=-1;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		can &= x;
		A[x] = (-1)^x;
	}
	FOR(i,20) FOR(x,1<<20) A[x&(~(1<<i))] |= A[x];
	
	int ret=(can!=0);
	for(i=0;i<=1000000;i++) if((i|A[i])==-1) ret++;
	cout<<ret<<endl;
}

まとめ

今回のテクは色々使えそう。