問題一覧 > 通常問題

No.2300 Substring OR Sum

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

問題文

長さが NN である非負整数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) が与えられます．

1≤L≤R≤N1 \leq L \leq R \leq N を満たす整数対 (L,R)(L, R) に対して，f(L,R)=AL∨AL+1∨⋯∨ARf(L, R) = A_L \lor A_{L+1} \lor \dots \lor A_R と定めます．ただし x∨yx \lor y は xx と yy の bitwise OR です．

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

この問題の制約下で，答えは 2632^{63} 未満であることが示せます．

bitwise OR とは（クリックで展開）

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

  • X∨YX \lor Y を 22 進表記したときの 2k2^k (k≥0)(k \geq 0) の位は、XX の 22 進表記での 2k2^k の位と、 YY の 22 進表記での 2k2^k の位のうち少なくとも一方が 11 である場合 11 、そうでない場合 00

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

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

制約

  • 入力は全て整数
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤Ai<2280 \leq A_i \lt 2^{28}

入力

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

NN
A1A_1 A2A_2 …\dots ANA_N

出力

答えを出力せよ．

サンプル

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

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

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

よって，答えは 3+3+7+1+5+4=233 + 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もしくは右上の雲マークをクリックしてアカウントを作成してください。