No.3594 Subset OR
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 :
PCTprobability
/ テスター :
lif4635
タグ : / 解いたユーザー数 17
作問者 :
PCTprobability
/ テスター :
lif4635
問題文最終更新日: 2026-07-23 20:07:47
問題文
長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。以下の条件を満たす非負整数 $x$ の個数を求めてください。
- ある $i(1 \le i \le N)$ が存在して $x\ \mathrm{OR}\ A_i = A_i$ が成り立つ。ここで、$\mathrm{OR}$ はビットごとの論理和を表す。
制約
- $1 \le N \le 2 \times 10^5$
- $0 \le A_i < 2^{30}$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1\ A_2\ \dots\ A_N$
出力
答えを出力せよ。
サンプル
サンプル1
入力
2 1 2
出力
3
$x = 0,1,2$ の $3$ 個が条件を満たします。
サンプル2
入力
3 5 6 8
出力
7
$x = 0,1,2,4,5,6,8$ の $7$ 個が条件を満たします。
サンプル3
入力
20 109983720 842017823 313708361 424086748 127766049 807103220 1059922944 748084749 770159538 595756156 353159883 4847225 830367602 440518558 429663756 517678552 668181045 926849958 326443945 602041346
出力
1770302
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。