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

时间限制3.00s

内存限制1.00GB

给定正整数 N,M,K 以及非负整数序列 A=(A1​,A2​,…,AN​)。

对于任意非空的非负整数序列 B=(B1​,B2​,…,B∣B∣​)，定义其得分如下：

• 当 B 的长度是 M 的倍数时，得分为 (B1​⊕B2​⊕⋯⊕B∣B∣​)K；

• 否则得分为 0。

其中，⊕ 表示按位异或运算。

请计算 A 的所有非空子序列（共 2N−1 个）各自的得分之和，并对 998244353 取模后输出。

按位异或的定义如下：对于非负整数 A,B，A⊕B 的二进制表示中，第 2k 位（k≥0）的数等于 A,B 的二进制表示中第 2k 位的数中恰有一个为 1 时为 1，否则为 0。

例如，3⊕5=6（二进制表示为：011⊕101=110）。 一般地，k 个整数 p1​,…,pk​ 的异或为 (⋯((p1​⊕p2​)⊕p3​)⊕⋯⊕pk​)，并且可以证明其结果与顺序无关。

输入格式

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

N M K A1​ A2​ … AN​

输出格式

请输出答案。

输入输出样例

输入 #1复制

3 2 2
1 2 3

输出 #1复制

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

说明/提示

限制条件

• 1≤N,K≤2×105

• 1≤M≤100

• 0≤Ai​<220

• 所有输入均为整数

样例解释 1

A 的所有非空子序列（共 23−1=7 个）各自的得分如下：

• (1)：0

• (2)：0

• (3)：0

• (1,2)：(1⊕2)2=9

• (1,3)：(1⊕3)2=4

• (2,3)：(2⊕3)2=1

• (1,2,3)：0

因此，总和为 0+0+0+9+4+1+0=14。

//洛谷题库提供题目，仅供学习使用

洛谷原题：https://www.luogu.com.cn/problem/AT_abc367_g

难度🌟🌟🌟🌟🌟🌟🌟

我的一辈子

欢迎大佬帮我解答题目，球球了！！！

HELP ME!!!!

积极评论会带来好运哦~~~~