与或AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\dots,A_N)$ and an integer $K$.
给定一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$ 和一个整数 $K$。AI (CI翻译)
Initially, $x=0$. For $i=1,2,\dots,N$ in this order, let us choose one of the following two operations to perform.
初始时，$x=0$。按照 $i=1,2,\dots,N$ 的顺序，对每个 $i$ 选择以下两种操作之一执行。AI (CI翻译)
- Operation
$1$: Replace$x$with$x$${\rm AND}$$A_i$. - Operation
$2$: Replace$x$with$x$${\rm OR}$$A_i$.
- 操作
$1$：将$x$替换为$x$${\rm AND}$$A_i$。 - 操作
$2$：将$x$替换为$x$${\rm OR}$$A_i$。
Here, operation $2$ must be chosen at most $K$ times in total. ${\rm AND}$ denotes the bitwise ${\rm AND}$ operation, and ${\rm OR}$ denotes the bitwise ${\rm OR}$ operation.
其中，操作 $2$ 总共最多可以选择 $K$ 次。${\rm AND}$ 表示按位与运算，${\rm OR}$ 表示按位或运算。AI (CI翻译)
Let $M$ be the maximum possible value of $x$ after all operations are finished. Find the number, modulo $998244353$, of operation sequences such that the final $x$ equals $M$.
设所有操作完成后 $x$ 的最大可能值为 $M$。请计算最终 $x$ 等于 $M$ 的操作序列数量，并对 $998244353$ 取模。AI (CI翻译)
Here, two operation sequences are distinguished if and only if there exists an integer $j$ ($1 \le j \le N$) such that the operation chosen at the $j$-th step differs between them.
当且仅当存在一个整数 $j$（$1 \le j \le N$），使得两个操作序列在第 $j$ 步选择的操作不同，这两个操作序列才视为不同。AI (CI翻译)
$T$ test cases are given; solve each of them.
给定 $T$ 组测试数据，请分别求解。AI (CI翻译)
What is the bitwise $\mathrm{AND}$ operation? The bitwise $\mathrm{AND}$ of non-negative integers $A, B$, denoted $A\ \mathrm{AND}\ B$, is defined as follows. The digit in the $2^k$ ($k \geq 0$) place of the binary representation of $A\ \mathrm{AND}\ B$ is $1$ if the corresponding digits of $A$ and $B$ in binary are both $1$, and $0$ otherwise. For example, $3\ \mathrm{AND}\ 5 = 1$ (in binary: $011\ \mathrm{AND}\ 101 = 001$).
什么是按位 $\mathrm{AND}$ 运算？对于非负整数 $A,B$，其按位 $\mathrm{AND}$ 运算记作 $A\ \mathrm{AND}\ B$，定义如下：在 $A\ \mathrm{AND}\ B$ 的二进制表示中，$2^k$（$k \geq 0$）位上的数字为 $1$，当且仅当 $A$ 和 $B$ 的二进制表示中对应位上的数字都为 $1$；否则为 $0$。例如，$3\ \mathrm{AND}\ 5 = 1$（二进制表示为：$011\ \mathrm{AND}\ 101 = 001$）。AI (CI翻译)
What is the bitwise $\mathrm{OR}$ operation? The bitwise $\mathrm{OR}$ of non-negative integers $A, B$, denoted $A\ \mathrm{OR}\ B$, is defined as follows. The digit in the $2^k$ ($k \geq 0$) place of the binary representation of $A\ \mathrm{OR}\ B$ is $1$ if at least one of the corresponding digits of $A$ and $B$ in binary is $1$, and $0$ otherwise. For example, $3\ \mathrm{OR}\ 5 = 7$ (in binary: $011\ \mathrm{OR}\ 101 = 111$).
什么是按位 $\mathrm{OR}$ 运算？对于非负整数 $A,B$，其按位 $\mathrm{OR}$ 运算记作 $A\ \mathrm{OR}\ B$，定义如下：在 $A\ \mathrm{OR}\ B$ 的二进制表示中，$2^k$（$k \geq 0$）位上的数字为 $1$，当且仅当 $A$ 和 $B$ 的二进制表示中对应位上的数字至少有一个为 $1$；否则为 $0$。例如，$3\ \mathrm{OR}\ 5 = 7$（二进制表示为：$011\ \mathrm{OR}\ 101 = 111$）。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \le T \le 10^4$$1 \le K \le N \le 2 \times 10^5$$0 \le A_i < 2^{60}$- The sum of
$N$in each input is at most$2 \times 10^5$. - All input values are integers.
$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$。 - 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:
输入从标准输入按以下格式给出，其中 $\mathrm{case}_i$ 表示第 $i$ 组测试数据：AI (CI翻译)
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_TT
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_TEach test case is given in the following format:
每组测试数据按以下格式给出：AI (CI翻译)
N K
A_1 A_2 \dots A_NN K
A_1 A_2 \dots A_NOutput
输出格式
AI (CI翻译)Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.
输出 $T$ 行。第 $i$ 行应包含第 $i$ 组测试数据的答案。AI (CI翻译)
样例
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
3
1
26
1
603979768
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。