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

输入格式

输入按照标准输入给出，格式如下： $N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

3 2 2
1 2 3

14

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

252000000

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

432440016

提示

$1 \leq N,K \leq 2 \times 10^5$ $1 \leq M \leq 100$ 0 \leq A_i < 2^{20} 所有输入值均为整数。以下是 $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$.

标签: AtCoder|abc367G

来源

AtCoder|abc367G