問題一覧 > 通常問題

No.2300 Substring OR Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : ShirotsumeShirotsume / テスター : stoqstoq ygussanyygussany
3 ProblemId : 9279 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-26 22:02:44

問題文

長さが $N$ である非負整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます.

$1 \leq L \leq R \leq N$ を満たす整数対 $(L, R)$ に対して,$f(L, R) = A_L \lor A_{L+1} \lor \dots \lor A_R$ と定めます.ただし $x \lor y$ は $x$ と $y$ の bitwise OR です.

$\displaystyle \sum_{L = 1}^{N} \sum_{R = L}^{N} f(L, R)$ を求めてください.

この問題の制約下で,答えは $2^{63}$ 未満であることが示せます.

bitwise OR とは(クリックで展開)

$2$ つの非負整数 $X, Y$ について、$X$ と $Y$ の bitwise OR $X \lor Y$ は以下のように定義されます。

  • $X \lor Y$ を $2$ 進表記したときの $2^k$ $(k \geq 0)$ の位は、$X$ の $2$ 進表記での $2^k$ の位と、 $Y$ の $2$ 進表記での $2^k$ の位のうち少なくとも一方が $1$ である場合 $1$ 、そうでない場合 $0$

例えば、 $3 \lor 5 = 7, 1 \lor 1 = 1$ です。

一般に $k$ 個の非負整数 $p_1, p_2, \dots, p_k$ の bitwise OR は $( \dots ((p_1 \lor p_2) \lor p_3) \lor \dots) \lor p_k)$ と定義され、これは $p_1, p_2, \dots, p_k$ の順番によらないことが証明できます。

制約

  • 入力は全て整数
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \lt 2^{28}$

入力

入力は標準入力から以下の形式で与えられる.

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

出力

答えを出力せよ.

サンプル

サンプル1
入力
3
3 1 4
出力
23

$1 \leq L \leq R \leq N$ を満たす整数組 $(L, R)$ それぞれについて $f$ を計算した結果は以下の通りです.

  • $f(1, 1) = 3$
  • $f(1, 2) = 3 \lor 1 = 3$
  • $f(1, 3) = 3 \lor 1 \lor 4 = 7$
  • $f(2, 2) = 1$
  • $f(2, 3) = 1 \lor 4 = 5$
  • $f(3, 3) = 4$

よって,答えは $3 + 3 + 7 + 1 + 5 + 4 = 23$ です.

サンプル2
入力
10
3 1 4 1 5 9 2 6 5 3
出力
557
サンプル3
入力
12
199586018 156804892 244487299 216787549 253642240 22651348 151822338 228911339 252243011 162715305 201651504 4294095
出力
19348547260

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