P16594 [GKS 2016 #E] Partioning Number
题目描述
Shekhu 有 $N$ 个球。她想把它们分配到一个或多个桶中，并满足以下所有约束条件：
1. 从左到右读取时，桶中的球数必须呈非递减顺序。
2. 最左边的桶必须非空，且最左边桶中的球数必须能被 $D$ 整除。
3. **任意**两个桶之间的球数之差（并不仅是相邻桶）必须小于或等于 $2$。
Shekhu 有多少种不同的分配方式？如果从左到右读取桶中球数的列表不同，则认为两种方式不同。
输入格式
输入的第一行给出测试用例的数量 $T$。
接下来有 $T$ 个测试用例。每个测试用例由一行两个整数 $N$ 和 $D$ 组成，含义如上所述。
输出格式
对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述答案。
说明/提示
在样例 #1 中，可能的分布为：
```
1 1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 3
1 1 1 2 2
1 2 2 2
1 1 2 3
1 3 3
2 2 3
3 4
7
```
注意，`1 2 4` 不是有效的分布，因为 1 和 4 之间的差值大于 2。
在样例 #2 中，可能的分布为：
```
2 2 3
```
`3 4` 不可行，因为第一项不能被 2 整除。
在样例 #3 中，不存在可行的排列。
### 限制条件
$1 \le T \le 100$。
$1 \le D \le 100$。
**小数据集（测试集 1 – 可见）**
$1 \le N \le 2000$。
**大数据集（测试集 2 – 隐藏）**
$1 \le N \le 10^5$。
翻译由 DeepSeek V4 Pro 完成