これは思いつけて良かった。
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; }
まとめ
今回のテクは色々使えそう。