AT_abc367_g [ABC367G] Sum of (XOR^K or 0)

题目描述

给定正整数 $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$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数等于 $A, B$ 的二进制表示中第 $2^k$ 位的数中恰有一个为 $1$ 时为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。 一般地，$k$ 个整数 $p_1, \dots, p_k$ 的异或为 $(\cdots((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$，并且可以证明其结果与顺序无关。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 2 2
1 2 3

输出 #1

14

输入输出样例 #2

输入 #2

10 5 3
100 100 100 100 100 100 100 100 100 100

输出 #2

252000000

输入输出样例 #3

输入 #3

16 4 100
7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558

输出 #3

432440016

说明/提示

限制条件

• $1 \leq N, K \leq 2 \times 10^5$
• $1 \leq M \leq 100$
• $0 \leq A_i < 2^{20}$
• 所有输入均为整数

样例解释 1

$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$。

由 ChatGPT 4.1 翻译