\(X\) の \(2\) 進数表記で立っているビットが全て \(Y\) でも立っていることを \(X\subset Y\) と表すことにします。

この問題で、ある整数 \(K\) が箱に入れられる必要十分条件は、\(A_i\subset K\) となるすべての \(A_i\) の論理和が \(K\) になることです。 これを \(1\leq K<2^{20}\) について求めることを考えます。 これは、次のコードに示すような DP をすることで、\(O(N+max(A)\log(max(A)))\) で解くことができます。

#include <iostream>
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define REP(i, n) for (int i = 1; i <= int(n); i++)
int N, dp[1050000];
int main() {
	std::cin >> N;
	rep(i, N) {
		int A;
		std::cin >> A;
		dp[A] = A;
	}
	int ans = 0;
	REP(i, (1 << 20) - 1) {
		ans += dp[i] == i;
		rep(j, 20) dp[i | (1 << j)] |= dp[i];
	}
	std::cout << ans << std::endl;
}