分数: 800 点
问题陈述
给你正整数 N,M.
求模数 998244353,非负整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N 满足以下所有条件。
- 0\le A_i < 2^M (1\le i\le N)
- \operatorname{popcount}(A_i\oplus A_j) \le 2 (1\le i < j\le N)
这里,对于非负整数 x,y,我们表示为 x\oplus y 按位 \mathrm{XOR} 的操作 x 和 y,并通过 \operatorname{popcount}(x) 的 popcount x.
你被给予 T 测试用例,因此找到每个用例的答案。
什么是按位 \mathrm{XOR} 操作?
按位 \mathrm{XOR} 非负整数 A, B,表示 A \oplus B定义如下。
- 当 A \oplus B 以二进制形式写入,其中的数字 2^k (k \geq 0)地方是 1 如果恰好是以下之一 A, B 有 当以二进制形式写入时,位于 1 在 2^k 位置,并且 0 否则。
什么是popcount?
对于非负整数 x, \operatorname{popcount}(x) 是数量 1s 当 x 以二进制形式写入。更准确地说,对于非负整数 二进制的 x 这样 \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace),我们有 \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.
例如, 13 是1101,所以我们有 \operatorname{popcount}(13)=3.
约束
- 1\le T\le 2\times 10^5
- 2\le N,M < 998244353
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N M
输出
输出 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 2 3 7 2 2025 200
示例输出 1
56 16384 549499339
考虑第一个测试用例。
例如, A=(4,5) 满足条件,因为每个元素都在 0 和 2^3-1=7,和 \operatorname{popcount}(4\oplus 5)=\operatorname{popcount}(1)=1\le 2。另一方面,两者都没有 A=(2,5) 也不 A=(0,7) 满足条件。
有 56 序列 A 满足条件,所以输出 56 在第一行。