問題一覧 > 通常問題

No.3662 yuu Hates Sigma Problem

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 68
作問者 : yuusaan / テスター : dyktr_06 sepa38 くらげ t5ugu
お気に入りにしたユーザー ProblemId : 13270 / 自分の提出
問題文最終更新日: 2026-08-30 01:56:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 022 (順位表) の他の問題:

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.
Subtasks

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もしくは右上の雲マークをクリックしてアカウントを作成してください。