#P17732. [ICPC 2019 Xuzhou R] Cats line up
[ICPC 2019 Xuzhou R] Cats line up
题目描述
今天,你来到了一个猫村。这个村子里有 只猫。每只猫都非常可爱,并且所有 只猫都非常聪明,它们排成了一排。
这个村子里的猫非常特别!!!为什么这么说呢?因为这些猫的身高互不相同,且都是 到 之间(包含两端)的整数。
众所周知,谁都不喜欢拍照时站在太高的人旁边,因为站在那样的人旁边会显得自己很矮。人是这样,猫也是如此。
每只猫都希望与它相邻的猫的身高差不超过 。如果一只猫与它的每个邻居的身高差都不超过 ,它就会感到开心。
现在,给定这个村子里猫的数量以及猫所能接受的身高差 ,你能计算出有多少种让所有猫都开心的排队方式吗?
输入格式
第一行包含一个整数 ,表示你需要计算的 的对数。 接下来的 行,每行包含两个整数 和 。
输出格式
对于每组测试数据,输出一行一个整数 —— 使得所有猫都开心的排队方案数对 取模的结果。
18
1 1
2 2
3 2
1 3
2 3
3 3
4 3
5 3
6 3
7 3
8 3
9 3
10 3
11 3
12 3
13 3
14 3
15 3
1
2
6
1
2
6
24
72
180
428
1042
2512
5912
13592
30872
69560
155568
345282
提示
翻译由 DeepSeek V4 Pro 完