← 返回题目列表

Codeforces · 2238/F

F. 无限的工作

中文机器翻译题面 查看原题
更多的猴子!
— 指数空闲

您负责一个研究不寻常函数的大型科学项目。为了实现这一目标,您雇佣了 $$$10^{10^{100}}$$$ 学生,并用自然数对他们进行编号,从 $$$1$$$ 到 $$$10^{10^{100}}$$$。学生们形成一个层次结构:

  • 学生$$$1$$$是主要的。
  • 对于任何$$$i \geq 2$$$,学生$$$i$$$的直接主管是学生$$$\left\lfloor \frac{i}{2} \right\rfloor$$$。
  • 学生$$$i$$$的直接下属是学生$$$2i$$$和$$$2i+1$$$(如果这些数字不超过$$$10^{10^{100}}$$$)。
  • 从属关系是及物的:如果 $$$a$$$ 从属于 $$$b$$$,并且 $$$b$$$ 从属于 $$$c$$$,则 $$$a$$$ 从属于 $$$c$$$。
最初,所有学生都在工作。

距离项目完成还剩 $$$n$$$ 天。每天由两个阶段组成:

  • 招聘。 每个在职学生 $$$i$$$ 雇用所有直接隶属于他的非在职学生:
    • 如果学生 $$$2i$$$ 不工作且 $$$2i \leq 10^{10^{100}}$$$,则他开始工作。
    • 如果学生 $$$2i + 1$$$ 不工作并且 $$$2i + 1 \leq 10^{10^{100}}$$$,他开始工作。
    新录用的学生不能在同一天聘用任何人。
  • 射击。 您可以选择任何一组在职学生,并且 直接 直接地 解雇他们每个人。如果学生$$$i$$$被直接解雇,那么他的所有下属也将自动被解雇。这种解雇被称为 间接。学生 $$$1$$$ 不能被解雇。

附加限制: 每个学生最多可以被解雇(直接或间接)一次。如果先前被解雇的学生再次被聘用,则禁止执行会导致该学​​生再次被解雇的解雇行为。

下面(仅显示前 $$$15$$$ 学生)是如何选择每天直接解雇学生的示例,以便在 $$$2$$$ 天后准确地留下 $$$5$$$ 学生。顶部的数字对应学号,边缘表示从属关系。

正在工作但尚未被解雇的学生标记为绿色,已被解雇的学生标记为白色,之前被解雇但已重新雇用的学生标记为红色。

天$$$1$$$,开火前。所有学生均被聘用。 天 $$$1$$$,射击后。学生 $$$2$$$、$$$6$$$、$$$7$$$ 被解雇。 天$$$2$$$,开火前。学生 $$$2$$$、$$$6$$$、$$$7$$$ 被雇用。请注意,在解雇阶段,学生 $$$3$$$ 不能被直接解雇,因为这会导致解雇在此之前已经被解雇的学生 $$$6$$$ 和 $$$7$$$。

您的目标是让 $$$n$$$ 天后,项目中正好剩下 $$$k$$$ 在职学生。同时,您需要最大限度地减少整个期间的直接射击总数。

求每天选择直接解雇学生的方式数,使得最终在职学生的数量为$$$k$$$,并且直接解雇的总数尽可能小。输出对 $$$10^9 + 7$$$ 取模的答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — 天数和所需的最终活跃学生人数。

输出

对于每个测试用例,输出一个整数 - 每天选择解雇的可能方法的数量,以便在解雇总数尽可能少的情况下,在 $$$n$$$ 天后,恰好有 $$$k$$$ 学生留下来。

示例

输入
复制

6
1 1
2 5
3 4
1 5
20 14
1000000000 20

输出
复制

1
2
2
42
120
12

注意

第一个测试用例中,有$$$1$$$方式:第一天,直接解雇编号为$$$2$$$和$$$3$$$的学生。只剩下一名学生,编号为 $$$1$$$。

在第二个测试用例中,有 $$$2$$$ 可能的方法:

  • 第一天,直接解雇了编号为$$$2$$$、$$$6$$$、$$$7$$$的学生。学生 $$$1$$$ 和 $$$3$$$ 留下。第二天一开始,他们就雇用了编号为 $$$2$$$、$$$6$$$ 和 $$$7$$$ 的学生。
  • 第一天,直接解雇了编号为$$$3$$$、$$$4$$$、$$$5$$$的学生。学生 $$$1$$$ 和 $$$2$$$ 留下。第二天一开始,他们就雇用了编号为 $$$3$$$、$$$4$$$ 和 $$$5$$$ 的学生。
可以证明,不可能通过解雇少于三名学生来结束 $$$5$$$ 学生。

在第三个测试用例中,有 $$$2$$$ 可能的方法:

  • 第一天,直接解雇学生$$$3$$$。第二天,学生 $$$1$$$ 雇用学生 $$$3$$$。我们解雇任何人。第三天,学生 $$$3$$$ 雇用学生 $$$6$$$ 和 $$$7$$$。之后,直接解雇学生$$$2$$$。因此,$$$4$$$ 学生仍然是:$$$1$$$、$$$3$$$、$$$6$$$ 和 $$$7$$$。
  • 第一天,直接解雇学生$$$2$$$。第二天,学生 $$$1$$$ 雇用学生 $$$2$$$。我们解雇任何人。第三天,学生 $$$2$$$ 雇用学生 $$$4$$$ 和 $$$5$$$。之后,直接解雇学生$$$3$$$。因此,$$$4$$$ 学生仍然是:$$$1$$$、$$$2$$$、$$$4$$$ 和 $$$5$$$。
可以证明,直接解雇少于两名学生是不可能以 $$$4$$$ 学生结束的。