パ研合宿2020 第1日「SpeedRun」 : M - 貢ぎ物

意外に手間取った。
https://atcoder.jp/contests/pakencamp-2020-day1/tasks/pakencamp_2020_day1_m

問題

整数の集合が与えられる。
2要素を選びそのbitwise-orを取った値を集合に追加する処理を任意に繰り返す場合、最終的に集合の要素は最大何通りにできるか。

解法

A[x] := (x&y)=yとなるような要素同士のbitwise-orで作れる要素のbitwise-or
とする。初期状態で集合中にxが含まれるならA[x]=xだし、そうでなければA[x]=0である。
その後は、高速ゼータ変換の要領で1bitだけ立っている整数zを用いてA[x|z] |= A[x]を繰り返していこう。

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

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

まとめ

高速ゼータ変換を使うことはすぐ思いついたけど、その後に手間取ったり。