分数: 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) 表示以下问题的答案:
考虑组成一些卡片对。
每对由两张不同的卡组成,并且这两张卡上写入的整数的按位异或必须等于 X。 同一张卡不能包含在多对中。
找出在这些条件下可以形成的最大对数。
输出以下值:
\[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 \]
什么是按位 \mathrm{XOR} 操作
按位 \mathrm{XOR} 非负整数 A, B, A \oplus B定义如下。
- 处的数字 2^k (k \geq 0) 地点 A \oplus B 的二进制表示是 1 如果恰好是位于的数字之一 2^k 地点 A 和 B 的二进制表示是 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\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) 。
- 对于 X=1:可以形成零对。
- 对于 X=2:两对 可以形成 (A_1,A_4) 和 (A_2,A_3) 。
- 对于 X=3:可以形成零对。
因此, 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