103676: [Atcoder]ABC367 G - Sum of (XOR^K or 0)
Description
Score : $675$ points
Problem Statement
You are given positive integers $N$, $M$, $K$, and a sequence of non-negative integers: $A=(A_1,A_2,\ldots,A_N)$.
For a non-empty non-negative integer sequence $B=(B_1,B_2,\ldots,B_{|B|})$, we define its score as follows.
- If the length of $B$ is a multiple of $M$: $(B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K$
- Otherwise: $0$
Here, $\oplus$ represents the bitwise XOR.
Find the sum, modulo $998244353$, of the scores of the $2^N-1$ non-empty subsequences of $A$.
What is bitwise XOR?
The bitwise XOR of non-negative integers $A$ and $B$, denoted as $A \oplus B$, is defined as follows:- In the binary representation of $A \oplus B$, the digit at position $2^k$ ($k \geq 0$) is $1$ if exactly one of $A$ and $B$ has a $1$ in that position in their binary representations, and $0$ otherwise.
In general, the XOR of $k$ integers $p_1, \dots, p_k$ is defined as $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$, and it can be proved that this is independent of the order of $p_1, \dots, p_k$.
Constraints
- $1 \leq N,K \leq 2 \times 10^5$
- $1 \leq M \leq 100$
- $0 \leq A_i < 2^{20}$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the answer.
Sample Input 1
3 2 2 1 2 3
Sample Output 1
14
Here are the scores of the $2^3-1=7$ non-empty subsequences of $A$.
- $(1)$: $0$
- $(2)$: $0$
- $(3)$: $0$
- $(1,2)$: $(1\oplus2)^2=9$
- $(1,3)$: $(1\oplus3)^2=4$
- $(2,3)$: $(2\oplus3)^2=1$
- $(1,2,3)$: $0$
Therefore, the sought sum is $0+0+0+9+4+1+0=14$.
Sample Input 2
10 5 3 100 100 100 100 100 100 100 100 100 100
Sample Output 2
252000000
Sample Input 3
16 4 100 7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558
Sample Output 3
432440016
Output
得分：$675$分
问题陈述
给定正整数$N$，$M$，$K$，以及一个非负整数序列：$A=(A_1,A_2,\ldots,A_N)$。
对于一个非空非负整数序列$B=(B_1,B_2,\ldots,B_{|B|})$，我们定义其得分如下。
- 如果$B$的长度是$M$的倍数：$(B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K$
- 否则：$0$
这里，$\oplus$表示按位异或。
找出$A$的$2^N-1$个非空子序列的得分之和，对$998244353$取模。
什么是按位异或？
非负整数$A$和$B$的按位异或，记作$A \oplus B$，定义如下：- 在$A \oplus B$的二进制表示中，位置$2^k$（$k \geq 0$）的数字是$1$，如果$A$和$B$在它们二进制表示中的该位置上恰好有一个是$1$，否则是$0$。
一般地，$k$个整数$p_1, \dots, p_k$的异或定义为$((\cdots (p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$，可以证明这与$p_1, \dots, p_k$的顺序无关。
约束条件
- $1 \leq N,K \leq 2 \times 10^5$
- $1 \leq M \leq 100$
- $0 \leq A_i < 2^{20}$
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出：
$N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$
输出
打印答案。
示例输入 1
3 2 2 1 2 3
示例输出 1
14
以下是$A$的$2^3-1=7$个非空子序列的得分。
- $(1)$: $0$
- $(2)$: $0$
- $(3)$: $0$
- $(1,2)$: $(1\oplus2)^2=9$
- $(1,3)$: $(1\oplus3)^2=4$
- $(2,3)$: $(2\oplus3)^2=1$
- $(1,2,3)$: $0$
因此，所求和为$0+0+0+9+4+1+0=14$。
示例输入 2
10 5 3 100 100 100 100 100 100 100 100 100 100
示例输出 2
252000000