No.3768 Sum of Difference of XOR
タグ : / 解いたユーザー数 5
作問者 :
apricity
/ テスター :
👑 Problem Statement
You are given a sequence of non-negative integers $A = (A_1, A_2, \dots, A_N)$ of length $N$.
There are $\displaystyle\binom{N}{4}\cdot 4!$ possible (ordered) quadruples $(i,j,k,l)$ of distinct integers between $1$ and $N$, inclusive. Find the sum of $|(A_i \oplus A_j) - (A_k \oplus A_l)|$ over all of them, modulo $998244353$.
$\oplus$ denotes the bitwise exclusive OR.
Input
$N$ $A_1\ A_2\ \dots\ A_N$
- All inputs are integers.
- $4 \leq N \leq 2 \times 10^5$
- $0 \leq A_i < 2^{18}$
Output
Output the sum of $|(A_i \oplus A_j) - (A_k \oplus A_l)|$ over all possible $(i,j,k,l)$, modulo $998244353$.
Sample
Sample 1
Input
4 2 3 5 7
Output
40
The possible $(i,j,k,l)$ are the permutations of $(1,2,3,4)$, of which there are $24$.
For example, for $(i,j,k,l) = (1,2,3,4)$, we have $|(A_i \oplus A_j) - (A_k \oplus A_l)| = |(2\oplus 3)-(5\oplus 7)| = |1-2| = 1$.
Sample 2
Input
5 2 2 2 2 2
Output
0
Sample 3
Input
16 87337 191950 43849 77812 18819 99680 178310 18340 261512 213281 217502 206452 31309 176943 104288 155083
Output
607748709
Output the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。