← 返回题目列表

AtCoder · arc222_e

E. 异或匹配

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,按位 \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