No.3662 yuu Hates Sigma Problem
Problem Statement
You are given a positive integer $N$ and an array $A = (A_0,A_1,A_2,...,A_{N-1})$ of length $N$. Note that the indices start from $0$.
Find $\sum_{i=0}^{N-1} \sum_{j=0}^{N-1} A_i\cdot (j\oplus i)$ modulo $998244353$. (Here, $\oplus$ denotes the bitwise exclusive OR.)
Constraints
- $1\le N \le 5\times 10^5$
- $0\le A_i \le 5\times 10^5\ (0\le i \le N-1)$
- All inputs are integers.
This problem consists of multiple subtasks. You earn the partial score for a subtask if your output is correct for all cases satisfying that subtask's additional constraints.
$\mathrm{subtask1}.$ $N\le 3000.$ ($20$% of the points)
$\mathrm{subtask2}.$ $N$ is a power of $2$. That is, there exists a non-negative integer $x$ such that $N=2^x$. ($30$% of the points)
$\mathrm{subtask3}.$ No additional constraints. ($50$% of the points)
Input
$N$
$A_0\ A_1\ A_2\ \dots\ A_{N-1}$
Output
Print a newline at the end.
Sample
Sample 1
Input
4 3 4 5 6
Output
108
Detailed calculation
$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$
The value of the expression is $108$, so print $108$, its remainder when divided by $998244353$.
This sample satisfies the additional constraints of all subtasks.
Sample 2
Input
10 31 41 59 26 53 58 97 93 23 84
Output
34069
The samples do not include any case that requires this operation, but note that you must find the value of the expression modulo $998244353$.
This sample satisfies the additional constraints of $\mathrm{subtask1,3}$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
sepa38
くらげ