問題一覧 > 通常問題

No.3594 Subset OR

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : PCTprobability / テスター : lif4635
お気に入りにしたユーザー ProblemId : 13621 / 自分の提出
問題文最終更新日: 2026-07-23 20:07:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given a sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$ of length $N$. Find the number of non-negative integers $x$ satisfying the following condition.

  • There exists some $i(1 \le i \le N)$ such that $x\ \mathrm{OR}\ A_i = A_i$ holds. Here, $\mathrm{OR}$ denotes the bitwise logical OR.

Constraints

  • $1 \le N \le 2 \times 10^5$
  • $0 \le A_i < 2^{30}$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$A_1\ A_2\ \dots\ A_N$

Output

Output the answer.

Sample

Sample 1
Input
2
1 2
Output
3

The $3$ values $x = 0,1,2$ satisfy the condition.

Sample 2
Input
3
5 6 8
Output
7

The $7$ values $x = 0,1,2,4,5,6,8$ satisfy the condition.

Sample 3
Input
20
109983720 842017823 313708361 424086748 127766049 807103220 1059922944 748084749 770159538 595756156 353159883 4847225 830367602 440518558 429663756 517678552 668181045 926849958 326443945 602041346
Output
1770302

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。