No.2300 Substring OR Sum
タグ : / 解いたユーザー数 158
作問者 :
stoq
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もしくは右上の雲マークをクリックしてアカウントを作成してください。