No.3768 Sum of Difference of XOR
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 4
作問者 :
apricity
/ テスター :
👑 
AngrySadEight
タグ : / 解いたユーザー数 4
作問者 :
apricity
/ テスター :
👑
問題文最終更新日: 2026-10-06 20:33:29
yukicoder contest 518
(順位表)
の他の問題:
問題文
長さ $N$ の非負整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられます．
$1$ 以上 $N$ 以下の相異なる整数からなる（順序付き）四つ組 $(i,j,k,l)$ は $\displaystyle\binom{N}{4}\cdot 4!$ 通り考えられますが，それらすべてに対する $|(A_i \oplus A_j) - (A_k \oplus A_l)|$ の総和を $998244353$ で割った余りを求めてください．
$\oplus$ は bit ごとの排他的論理和を表します．
入力
$N$ $A_1\ A_2\ \dots\ A_N$
- 入力はすべて整数．
- $4 \leq N \leq 2 \times 10^5$
- $0 \leq A_i < 2^{18}$
出力
考えられるすべての $(i,j,k,l)$ に対する $|(A_i \oplus A_j) - (A_k \oplus A_l)|$ の総和を $998244353$ で割った余りを出力してください．
サンプル
サンプル1
入力
4 2 3 5 7
出力
40
$(i,j,k,l)$ として考えられるものは $(1,2,3,4)$ の並び替えで， $24$ 通りあります．
例えば， $(i,j,k,l) = (1,2,3,4)$ に対して， $|(A_i \oplus A_j) - (A_k \oplus A_l)| = |(2\oplus 3)-(5\oplus 7)| = |1-2| = 1$ です．
サンプル2
入力
5 2 2 2 2 2
出力
0
サンプル3
入力
16 87337 191950 43849 77812 18819 99680 178310 18340 261512 213281 217502 206452 31309 176943 104288 155083
出力
607748709
$998244353$ で割った余りを出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。