/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
N 枚のカードがあります．i 番目のカード（1\leq i\leq N）には整数 A_i が書かれています．ここで，0\leq A_i \leq 2^M-1 が成り立ちます．
各整数 X=0,1,\ldots,2^M-1 に対して，次の問題の答えを f(X) と書くことにします．
カードのペアをいくつか作ることを考えます．
ただし，ペアは相異なる 2 枚のカードからなり，それら 2 枚のカードに書かれた整数のビット単位 XOR が X となる必要があります． 同じカードを複数のペアに含めることはできません．
この条件のもとで作れるペアの個数の最大値を求めてください．
次の値を出力してください．
\[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR}，A \oplus B は，以下のように定義されます．
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は，A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1，そうでなければ 0 である．
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され，これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます．
制約
- 2\leq N\leq 2\times 10^5
- 1\leq M\leq 20
- 0\leq A_i \leq 2^M-1 (1\leq i\leq N)
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられます．
N M A_1 A_2 \ldots A_N
出力
次の値を出力してください．
\[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]
入力例 1
4 2 1 1 3 3
出力例 1
202
- X=0 の場合：(A_1,A_2)，(A_3,A_4) という 2 個のペアを作ることができます．
- X=1 の場合：0 個のペアを作ることができます．
- X=2 の場合：(A_1,A_4)，(A_2,A_3) という 2 個のペアを作ることができます．
- X=3 の場合：0 個のペアを作ることができます．
したがって，f(0)=2，f(1)=0，f(2)=2，f(3)=0 です．出力すべき値は 2\times 1 + 0\times 10 + 2\times 100 + 0\times 1000 = 202 です．
入力例 2
10 3 5 2 1 4 5 5 5 0 1 7
出力例 2
22332223
入力例 3
10 4 11 6 3 8 6 7 14 10 10 11
出力例 3
613668597
Score : 700 points
Problem Statement
There are N cards. The i-th card (1\leq i\leq N) has the integer A_i written on it. Here, 0\leq A_i \leq 2^M-1 holds.
For each integer X=0,1,\ldots,2^M-1, let f(X) denote the answer to the following problem:
Consider forming some pairs of cards.
Each pair consists of two distinct cards, and the bitwise XOR of the integers written on those two cards must equal X. The same card cannot be included in multiple pairs.
Find the maximum number of pairs that can be formed under these conditions.
Output the following value:
\[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]
What is the bitwise \mathrm{XOR} operation
The bitwise \mathrm{XOR} of non-negative integers A, B, A \oplus B, is defined as follows.
- The digit at the 2^k (k \geq 0) place of A \oplus B in binary representation is 1 if exactly one of the digits at the 2^k place of A and B in binary representation is 1, and 0 otherwise.
In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 2\leq N\leq 2\times 10^5
- 1\leq M\leq 20
- 0\leq A_i \leq 2^M-1 (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N
Output
Output the following value:
\[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]
Sample Input 1
4 2 1 1 3 3
Sample Output 1
202
- For X=0: two pairs (A_1,A_2) and (A_3,A_4) can be formed.
- For X=1: zero pairs can be formed.
- For X=2: two pairs (A_1,A_4) and (A_2,A_3) can be formed.
- For X=3: zero pairs can be formed.
Therefore, f(0)=2, f(1)=0, f(2)=2, and f(3)=0. The value to be output is 2\times 1 + 0\times 10 + 2\times 100 + 0\times 1000 = 202.
Sample Input 2
10 3 5 2 1 4 5 5 5 0 1 7
Sample Output 2
22332223
Sample Input 3
10 4 11 6 3 8 6 7 14 10 10 11
Sample Output 3
613668597