AT_arc222_e [ARC222E] XOR Matching

有 $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)$ 表示下面问题的答案： > 考虑从卡片中组成若干对。 > > 每一对都包含两张不同的卡片，并且这两张卡片上的整数的按位异或结果必须等于 $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$ 与 $B$ 的二进制表示中第 $2^k$ 位（$k \geq 0$）中恰有一个数字为 $1$，则 $A \oplus B$ 的第 $2^k$ 位为 $1$；否则为 $0$。 例如，$3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。 一般地，$k$ 个非负整数 $p_1, p_2, \ldots, p_k$ 的按位 $\mathrm{XOR}$ 定义为 $((\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots )\oplus p_k)$，可以证明，这与 $p_1, p_2, \ldots, p_k$ 的顺序无关。

输入按照以下格式从标准输入给出： > $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 - 对于 $X=0$：可以组成两对 $(A_1,A_2)$ 和 $(A_3,A_4)$。 - 对于 $X=1$：没有可行的配对，能组成 $0$ 对。 - 对于 $X=2$：可以组成两对 $(A_1,A_4)$ 和 $(A_2,A_3)$。 - 对于 $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\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$） - 所有输入值均为整数。 由 ChatGPT 5 翻译