AT_arc224_f [ARC224F] AND/OR

给定一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \dots, A_N)$ 和一个整数 $K$。 初始时，$x=0$。对于 $i=1,2,\dots,N$，按顺序对每一个 $A_i$，选择以下两种操作之一： - 操作 $1$：用 $x\,\mathrm{AND}\,A_i$ 替换 $x$； - 操作 $2$：用 $x\,\mathrm{OR}\,A_i$ 替换 $x$。 其中，操作 $2$ 总共最多只能选择 $K$ 次。$\mathrm{AND}$ 表示按位与运算，$\mathrm{OR}$ 表示按位或运算。 设 $M$ 为所有操作结束后可能获得的 $x$ 的最大值。请你求出有多少种操作序列，能使最终的 $x$ 等于 $M$。答案对 $998244353$ 取模。 注意：当且仅当存在某个整数 $j$（$1 \leq j \leq N$），使得两个方案在第 $j$ 步选择的操作不同，那么这两个操作序列才被视为不同。 给定 $T$ 组测试数据，请分别求解。 什么是按位 $\mathrm{AND}$ 运算？对于非负整数 $A,B$，$A\,\mathrm{AND}\,B$ 定义如下： - 在二进制下 $2^k$ 位的数字仅当 $A$ 和 $B$ 在对应位上都是 $1$ 时为 $1$，否则为 $0$。 例如，$3\,\mathrm{AND}\,5 = 1$（即二进制：$011\,\mathrm{AND}\,101=001$）。 什么是按位 $\mathrm{OR}$ 运算？对于非负整数 $A,B$，$A\,\mathrm{OR}\,B$ 定义如下： - 在二进制下 $2^k$ 位的数字只要 $A$ 或 $B$ 在对应位为 $1$ 就为 $1$，否则为 $0$。 例如，$3\,\mathrm{OR}\,5=7$（即二进制：$011\,\mathrm{OR}\,101=111$）。

输入通过标准输入给出，格式如下，其中 $\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 该输入包含五个测试用例。 对于第一个测试用例，$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$ 取模。 ### 数据范围 - $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$ - 所有输入均为整数。 由 ChatGPT 5 翻译