310730: CF1877C. Joyboard
Description
Chaneka, a gamer kid, invented a new gaming controller called joyboard. Interestingly, the joyboard she invented can only be used to play one game.
The joyboard has a screen containing $n+1$ slots numbered from $1$ to $n+1$ from left to right. The $n+1$ slots are going to be filled with an array of non-negative integers $[a_1,a_2,a_3,\ldots,a_{n+1}]$. Chaneka, as the player, must assign $a_{n+1}$ with an integer between $0$ and $m$ inclusive. Then, for each $i$ from $n$ to $1$, the value of $a_i$ will be equal to the remainder of dividing $a_{i+1}$ (the adjacent value to the right) by $i$. In other words, $a_i = a_{i + 1} \bmod i$.
Chaneka wants it such that after every slot is assigned with an integer, there are exactly $k$ distinct values in the entire screen (among all $n+1$ slots). How many valid ways are there for assigning a non-negative integer into slot $n+1$?
InputEach test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2\cdot10^4$) — the number of test cases. The following lines contain the description of each test case.
The only line of each test case contains three integers $n$, $m$, and $k$ ($1 \leq n \leq 10^9$; $0 \leq m \leq 10^9$; $1 \leq k \leq n+1$) — there are $n+1$ slots, the integer assigned in slot $n+1$ must not be bigger than $m$, and there should be exactly $k$ distinct values.
OutputFor each test case, output a line containing an integer representing the number of valid ways for assigning a non-negative integer into slot $n+1$.
ExampleInput4 4 6 3 2 0 1 265 265 265 3 10 2Output
2 1 0 5Note
In the first test case, one of the $2$ possible ways for Chaneka is to choose $a_{n+1}=6$. If she does that, then:
- $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]$
- There are $3$ distinct values.
In the second test case, the $1$ possible way for Chaneka is to choose $a_{n+1}=0$. If she does that, then $a = [0, 0, 0]$. There is only $1$ distinct value.
In the third test case, there is no possible way for assigning a non-negative integer into slot $n+1$.
Output
Chaneka，一个游戏爱好者，发明了一种名为“Joyboard”的新游戏控制器。这个控制器只能用来玩一个游戏。控制器有一个屏幕，包含从1到n+1编号的n+1个槽。这些槽将填充一个非负整数数组[a1,a2,a3,…,an+1]。Chaneka需要给an+1分配一个介于0到m（包括0和m）之间的整数。然后，对于每个从n到1的i，ai的值将等于ai+1（右侧的相邻值）除以i的余数。换句话说，ai = ai+1 mod i。Chaneka希望在进行分配后，整个屏幕（所有n+1个槽）中恰好有k个不同的值。问：有多少种有效的方法可以将非负整数分配到槽n+1中？
输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4）——测试用例的数量。接下来的每行包含一个测试用例的描述。
每个测试用例只有一行，包含三个整数n、m和k（1≤n≤10^9；0≤m≤10^9；1≤k≤n+1）——有n+1个槽，槽n+1中分配的整数不得大于m，且整个屏幕中应恰好有k个不同的值。
输出数据格式：
对于每个测试用例，输出一行，包含一个整数，表示将非负整数分配到槽n+1中的有效方法数量。
公式（用latex格式表示）：
$$ a_i = a_{i + 1} \bmod i $$
请注意，这是对题目内容的翻译和大意概述，并没有提供完整的解题方法或代码。题目大意： Chaneka，一个游戏爱好者，发明了一种名为“Joyboard”的新游戏控制器。这个控制器只能用来玩一个游戏。控制器有一个屏幕，包含从1到n+1编号的n+1个槽。这些槽将填充一个非负整数数组[a1,a2,a3,…,an+1]。Chaneka需要给an+1分配一个介于0到m（包括0和m）之间的整数。然后，对于每个从n到1的i，ai的值将等于ai+1（右侧的相邻值）除以i的余数。换句话说，ai = ai+1 mod i。Chaneka希望在进行分配后，整个屏幕（所有n+1个槽）中恰好有k个不同的值。问：有多少种有效的方法可以将非负整数分配到槽n+1中？ 输入数据格式： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2×10^4）——测试用例的数量。接下来的每行包含一个测试用例的描述。 每个测试用例只有一行，包含三个整数n、m和k（1≤n≤10^9；0≤m≤10^9；1≤k≤n+1）——有n+1个槽，槽n+1中分配的整数不得大于m，且整个屏幕中应恰好有k个不同的值。 输出数据格式： 对于每个测试用例，输出一行，包含一个整数，表示将非负整数分配到槽n+1中的有效方法数量。 公式（用latex格式表示）： $$ a_i = a_{i + 1} \bmod i $$ 请注意，这是对题目内容的翻译和大意概述，并没有提供完整的解题方法或代码。