No.3594 Subset OR
レベル :
/ AI推定難易度 : 2400
/ 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 :
PCTprobability
/ テスター :
lif4635
タグ : / 解いたユーザー数 18
作問者 :
PCTprobability
/ テスター :
問題文最終更新日: 2026-07-23 20:07:47
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。