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