分数: 450 点
问题陈述
给你正整数 N 和 K.
找到 总和,模数 998244353,所有正整数 x 不超过 N 并满足以下条件:
- 的 popcount x 正是 K.
你被给予 T 测试用例;解决它们中的每一个。
popcount是什么?
对于正整数 y, \mathrm{popcount}(y) 表示数量 二进制表示中的 1 位 y。 例如, \mathrm{popcount}(5)=2, \mathrm{popcount}(16)=1, \mathrm{popcount}(25)=3.约束
- 1 \leq T \leq 100
- 1 \leq N < 2^{60}
- 1 \leq K \leq 60
- T, N,和 K 是整数。
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
\mathrm{case}_i 表示 i- 第一个测试用例。 每个测试用例均按以下格式给出:
N K
输出
输出 T 行。 的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
2 20 2 1234567890 17
示例输出 1
100 382730918
对于第一个测试用例,有九个不超过的正整数 20 的 popcount 是 2: 3, 5, 6, 9, 10, 12, 17, 18, 20。他们的总和是 100.
时的余数 100 除以 998244353 is 100,所以输出 100 在第一行。
记住输出总和模数 998244353.