← 返回题目列表

AtCoder · abc406_e

H. 人口总数 3

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

分数: 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.