← 返回题目列表

AtCoder · abc367_g

G. (XOR^K 或 0) 之和

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,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