← 返回题目列表

Codeforces · 1877/C

C. 操纵板

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

Chaneka,一个游戏玩家,发明了一种称为游戏板的新游戏控制器。有趣的是,她发明的游戏板只能用来玩一种游戏。

游戏板有一个屏幕,其中包含从左到右从 $$$1$$$ 到 $$$n+1$$$ 编号的 $$$n+1$$$ 插槽。 $$$n+1$$$ 槽将填充非负整数数组 $$$[a_1,a_2,a_3,\ldots,a_{n+1}]$$$。 Chaneka 作为玩家,必须为 $$$a_{n+1}$$$ 分配一个介于 $$$0$$$ 和 $$$m$$$(含)之间的整数。然后,对于从 $$$n$$$ 到 $$$1$$$ 的每个 $$$i$$$,$$$a_i$$$ 的值将等于 $$$a_{i+1}$$$(右侧的相邻值)除以 $$$i$$$ 的余数。换句话说,$$$a_i = a_{i + 1} \bmod i$$$。

Chaneka 希望每个槽位分配一个整数后,整个屏幕(在所有 $$$n+1$$$ 槽位中)恰好有 $$$k$$$ 不同的值。将非负整数分配给槽 $$$n+1$$$ 有多少种有效方法?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2\cdot10^4$$$) — 测试用例的数量。以下行包含每个测试用例的描述。

每个测试用例的唯一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^9$$$; $$$0 \leq m \leq 10^9$$$; $$$1 \leq k \leq n+1$$$) — 有 $$$n+1$$$槽,槽 $$$n+1$$$ 中分配的整数不得大于 $$$m$$$,并且应该恰好有 $$$k$$$ 不同的值。

输出

对于每个测试用例,输出一行,其中包含一个整数,表示将非负整数分配到槽 $$$n+1$$$ 的有效方法的数量。

示例

输入 #1

4
4 6 3
2 0 1
265 265 265
3 10 2

输出 #1

2
1
0
5

注意

在第一个测试用例中,Chaneka 的 $$$2$$$ 可能方法之一是选择 $$$a_{n+1}=6$$$。如果她这样做,那么:

- $$$a_4=a_5\bmod 4=6\bmod 4=2$$$
- $$$a_3=a_4\bmod 3=2\bmod 3=2$$$
- $$$a_2=a_3\bmod 2=2\bmod 2=0$$$
- $$$a_1=a_2\bmod 1=0\bmod 1=0$$$
- $$$a = [0, 0, 2, 2, 6]$$$
- 有 $$$3$$$ 不同的值。

在第二个测试用例中,Chaneka 的 $$$1$$$ 可能的方式是选择 $$$a_{n+1}=0$$$。如果她这样做,那么 $$$a = [0, 0, 0]$$$。只有 $$$1$$$ 不同的值。

在第三个测试用例中,无法将非负整数分配到槽 $$$n+1$$$ 中。