問題一覧 > 通常問題

No.2300 Substring OR Sum

レベル : / AI推定難易度 : 950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 158
作問者 : Shirotsume / テスター : stoq ygussany
お気に入りにしたユーザー ProblemId : 9279 / 自分の提出
問題文最終更新日: 2023-04-26 22:02:44
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
yukicoder contest 388 (順位表) の他の問題:

Problem Statement

You are given a sequence of non-negative integers $A = (A_1, A_2, \dots, A_N)$ of length $N$.

For a pair of integers $(L, R)$ satisfying $1 \leq L \leq R \leq N$, define $f(L, R) = A_L \lor A_{L+1} \lor \dots \lor A_R$, where $x \lor y$ is the bitwise OR of $x$ and $y$.

Find $\displaystyle \sum_{L = 1}^{N} \sum_{R = L}^{N} f(L, R)$.

It can be shown that the answer is less than $2^{63}$ under the constraints of this problem.

What is bitwise OR? (click to expand)

For $2$ non-negative integers $X, Y$, the bitwise OR $X \lor Y$ of $X$ and $Y$ is defined as follows.

  • When $X \lor Y$ is written in base $2$, the digit in the $2^k$ $(k \geq 0)$ place is $1$ if at least one of the digit in the base $2$ representation of $X$ in the $2^k$ place and the digit in the base $2$ representation of $Y$ in the $2^k$ place is $1$, and $0$ otherwise.

For example, $3 \lor 5 = 7, 1 \lor 1 = 1$.

In general, the bitwise OR of $k$ non-negative integers $p_1, p_2, \dots, p_k$ is defined as $( \dots ((p_1 \lor p_2) \lor p_3) \lor \dots) \lor p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, \dots, p_k$.

Constraints

  • All input values are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \lt 2^{28}$

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
3
3 1 4
Output
23

The values of $f$ for each pair of integers $(L, R)$ satisfying $1 \leq L \leq R \leq N$ are as follows.

  • $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$

Therefore, the answer is $3 + 3 + 7 + 1 + 5 + 4 = 23$.

Sample 2
Input
10
3 1 4 1 5 9 2 6 5 3
Output
557
Sample 3
Input
12
199586018 156804892 244487299 216787549 253642240 22651348 151822338 228911339 252243011 162715305 201651504 4294095
Output
19348547260

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