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

    ID: 12696 传统题 3000ms 1024MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-FWT普通生成函数生成函数求系数计数 DP滚动数组快速幂

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

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

时间限制3.00s 内存限制1.00GB

题目描述

给定正整数 N,M,KN, M, K 以及非负整数序列 A=(A1,A2,…,AN)A=(A_1, A_2, \ldots, A_N)。

对于任意非空的非负整数序列 B=(B1,B2,…,B∣B∣)B=(B_1, B_2, \ldots, B_{|B|}),定义其得分如下:

  • 当 BB 的长度是 MM 的倍数时,得分为 (B1⊕B2⊕⋯⊕B∣B∣)K(B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K;
  • 否则得分为 00。

其中,⊕\oplus 表示按位异或运算。

请计算 AA 的所有非空子序列(共 2N−12^N-1 个)各自的得分之和,并对 998244353998244353 取模后输出。

按位异或的定义如下:对于非负整数 A,BA, B,A⊕BA \oplus B 的二进制表示中,第 2k2^k 位(k≥0k \geq 0)的数等于 A,BA, B 的二进制表示中第 2k2^k 位的数中恰有一个为 11 时为 11,否则为 00。

例如,3⊕5=63 \oplus 5 = 6(二进制表示为:011⊕101=110011 \oplus 101 = 110)。 一般地,kk 个整数 p1,…,pkp_1, \dots, p_k 的异或为 $(\cdots((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$,并且可以证明其结果与顺序无关。

输入格式

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

NN MM KK A1A_1 A2A_2 …\ldots ANA_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≤N,K≤2×1051 \leq N, K \leq 2 \times 10^5
  • 1≤M≤1001 \leq M \leq 100
  • 0≤Ai<2200 \leq A_i < 2^{20}
  • 所有输入均为整数

样例解释 1

AA 的所有非空子序列(共 23−1=72^3-1=7 个)各自的得分如下:

  • (1)(1):00
  • (2)(2):00
  • (3)(3):00
  • (1,2)(1,2):(1⊕2)2=9(1\oplus2)^2=9
  • (1,3)(1,3):(1⊕3)2=4(1\oplus3)^2=4
  • (2,3)(2,3):(2⊕3)2=1(2\oplus3)^2=1
  • (1,2,3)(1,2,3):00

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