分数: 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 表示按位异或。
求总和,模 998244353,得分 2^N-1 的非空子序列 A.
什么是按位异或?
非负整数的按位异或 A 和 B,表示为 A \oplus B,定义如下:- 在二进制表示中 A \oplus B,位置上的数字 2^k (k \geq 0) 是 1 如果恰好是其中之一 A 和 B 有一个 1 在其二进制表示中的该位置,以及 0 否则。
一般来说,XOR 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
以下是 2^3-1=7 的非空子序列 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
因此,求和为 0+0+0+9+4+1+0=14.
示例输入 2
10 5 3 100 100 100 100 100 100 100 100 100 100
示例输出 2
252000000
示例输入 3
16 4 100 7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558
示例输出 3
432440016