/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 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 はビットごとの排他的論理和を表します。
A の非空な部分列 2^N-1 個それぞれに対するスコアの総和を 998244353 で割った余りを求めてください。
ビットごとの排他的論理和とは
非負整数 A, B のビットごとの排他的論理和 A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に 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\lt 2^{20}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 2 2 1 2 3
出力例 1
14
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 です。
入力例 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
Score : 675 points
Problem Statement
You are given positive integers N, M, K, and a sequence of non-negative integers: A=(A_1,A_2,\ldots,A_N).
For a non-empty non-negative integer sequence B=(B_1,B_2,\ldots,B_{|B|}), we define its score as follows.
- If the length of B is a multiple of M: (B_1 \oplus B_2 \oplus \dots \oplus B_{|B|})^K
- Otherwise: 0
Here, \oplus represents the bitwise XOR.
Find the sum, modulo 998244353, of the scores of the 2^N-1 non-empty subsequences of A.
What is bitwise XOR?
The bitwise XOR of non-negative integers A and B, denoted as A \oplus B, is defined as follows:- In the binary representation of A \oplus B, the digit at position 2^k (k \geq 0) is 1 if exactly one of A and B has a 1 in that position in their binary representations, and 0 otherwise.
In general, the XOR of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k), and it can be proved that this is independent of the order of p_1, \dots, p_k.
Constraints
- 1 \leq N,K \leq 2 \times 10^5
- 1 \leq M \leq 100
- 0 \leq A_i < 2^{20}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
3 2 2 1 2 3
Sample Output 1
14
Here are the scores of the 2^3-1=7 non-empty subsequences of 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
Therefore, the sought sum is 0+0+0+9+4+1+0=14.
Sample Input 2
10 5 3 100 100 100 100 100 100 100 100 100 100
Sample Output 2
252000000
Sample Input 3
16 4 100 7053 3876 3178 8422 7802 5998 2334 6757 6889 6637 7365 9495 7848 9026 7312 6558
Sample Output 3
432440016