No.3662 yuu Hates Sigma Problem
yuusaan
dyktr_06
sepa38
くらげ
t5ugu問題文
正整数 $N$ と長さ $N$ の配列 $A = (A_0,A_1,A_2,...,A_{N-1})$ が与えられます。添え字が $0$ から始まる点に注意してください。
$\sum_{i=0}^{N-1} \sum_{j=0}^{N-1} A_i\cdot (j\oplus i)$ を $998244353$ で割ったあまりを求めてください。(ここで、$\oplus$ はビット毎の排他的論理和を表します。)
制約
- $1\le N \le 5\times 10^5$
- $0\le A_i \le 5\times 10^5\ (0\le i \le N-1)$
- 入力はすべて整数
本問題は複数の小課題からなる。小課題の追加制約を満たすケースすべてで正しい出力ができている場合、その小課題の部分点を獲得できる。
$\mathrm{subtask1}.$ $N\le 3000.$ (配点の $20$%)
$\mathrm{subtask2}.$ $N$ は $2$ べきである。すなわち、ある非負整数 $x$ が存在して $N=2^x$ を満たす。 (配点の $30$%)
$\mathrm{subtask3}.$ 追加の制約はない。 (配点の $50$%)
入力
$N$
$A_0\ A_1\ A_2\ \dots\ A_{N-1}$
出力
最後に改行してください。
サンプル
サンプル1
入力
4 3 4 5 6
出力
108
具体的な計算
$3\cdot(0\oplus 0) = 0$
$4\cdot(0\oplus 1) = 4$
$5\cdot(0\oplus 2) = 10$
$6\cdot(0\oplus 3) = 18$
$3\cdot(1\oplus 0) = 3$
$4\cdot(1\oplus 1) = 0$
$5\cdot(1\oplus 2) = 15$
$6\cdot(1\oplus 3) = 12$
$3\cdot(2\oplus 0) = 6$
$4\cdot(2\oplus 1) = 12$
$5\cdot(2\oplus 2) = 0$
$6\cdot(2\oplus 3) = 6$
$3\cdot(3\oplus 0) = 9$
$4\cdot(3\oplus 1) = 8$
$5\cdot(3\oplus 2) = 5$
$6\cdot(3\oplus 3) = 0$
式の値は $108$ なので $998244353$ で割ったあまりである $108$ を出力します。
このサンプルはすべての小課題の追加制約を満たします。
サンプル2
入力
10 31 41 59 26 53 58 97 93 23 84
出力
34069
サンプルにはこの処理が必要になるケースは含まれていませんが、式の値を $998244353$ で割ったあまりを求める点に注意してください。
このサンプルは $\mathrm{subtask1,3}$ の追加制約を満たします。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。