← 返回题目列表

AtCoder · arc224_f

F. 和/或

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

分数: 700 点

问题陈述

给你一个长度-N 非负整数序列 A=(A_1,A_2,\dots,A_N) 和一个整数 K.

最初, x=0。 对于 i=1,2,\dots,N 按照这个顺序,让我们选择以下两个操作之一来执行。

  • 操作 1 :替换 x 与 x {\rm AND} A_i.
  • 操作 2 :替换 x 与 x {\rm OR} A_i.

这里,操作 最多必须选择 2 总共 K 次。 {\rm AND} 表示按位 {\rm AND} 操作,以及 {\rm OR} 表示按位 {\rm OR} 操作。

让 M 是最大可能值 x 所有操作完成后。 求模数 998244353,操作序列使得最终 x 等于 M.

这里,区分两个操作序列当且仅当存在一个整数 j (1 \le j \le N)使得在 j第一步在它们之间有所不同。

T 给出了测试用例;解决它们中的每一个。

什么是按位 \mathrm{AND} 操作?

按位 \mathrm{AND} 非负整数 A, B,表示 A\ \mathrm{AND}\ B定义如下。

  • 中的数字 2^k (k \geq 0) 的二进制表示的位置 A\ \mathrm{AND}\ B is 1 如果相应的数字 二进制的 A 和 B 都是 1,和 0 否则。
例如, 3\ \mathrm{AND}\ 5 = 1 (二进制: 011\ \mathrm{AND}\ 101 = 001).

什么是按位 \mathrm{OR} 操作?

按位 \mathrm{OR} 非负整数 A, B,表示 A\ \mathrm{OR}\ B定义如下。

  • 中的数字 2^k (k \geq 0) 的二进制表示的位置 A\ \mathrm{OR}\ B is 1 如果至少有一位对应的数字 二进制的 A 和 B 是 每个输入中的 1,和 0 否则。
例如, 3\ \mathrm{OR}\ 5 = 7 (二进制: 011\ \mathrm{OR}\ 101 = 111).

约束

  • 1 \le T \le 10^4
  • 1 \le K \le N \le 2 \times 10^5
  • 0 \le A_i < 2^{60}
  • 总和 N 最多为 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{case}_i 表示 i-第一个测试用例:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N K
A_1 A_2 \dots A_N

输出

输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。


示例输入 1

5
5 3
3 7 1 2 6
1 1
1
10 8
3 1 4 1 5 9 2 6 5 3
10 5
227966327241983404 430356836747706085 918791034668488208 753980266897555955 1090352658151595591 1077218377572152409 641276315925917062 859382256805178767 103741332934325112 1090530740094421349
33 33
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

示例输出 1

3
1
26
1
603979768

此输入包含五个测试用例。

对于第一个测试用例, M=7,以下三个操作序列达到最终值 x=M.

  • 按顺序执行操作 1,1,2,2,2. x 更改为 0 \to 0 \to 0 \to 1 \to 3 \to 7.
  • 按顺序执行操作 1,2,1,2,2. x 更改为 0 \to 0 \to 7 \to 1 \to 3 \to 7.
  • 按顺序执行操作 2,1,1,2,2. x 更改为 0 \to 3 \to 3 \to 1 \to 3 \to 7.

对于第五个测试用例,请注意答案应该以模数形式输出 998244353.