3029. 不重复正整数

单点时限: 2.0 sec

内存限制: 256 MB

整数拆分是把一个正整数(简称为和数)拆分为一个或若干个指定正整数(简称为零数,通常不区别式中各零数的排列顺序)之和,这是一个有趣的计算问题。通常拆分式中的零数有重复和不重复(即拆分式中各零数互不相同)两种情况。

如果我们打算将一个给定的正整数 $N$ ($N\le 50$)拆分为若干个不重复的正整数($a_1+a_2+\cdots a_i,i \ge 1$)之和,其中每个零数的取值不大于给定的正整数 $M$ ($M\le 20$),即 $1 \le a_i \le M $,请问共有多少种不同的拆分方案。

输入格式

第 $1$ 行:一个整数 $T$ ($1 \le T \le 10$) 为问题数。

接下来共 $T$ 行整数,每行对应 $1$ 个问题,包含用一个空格隔开的两个正整数,分别表示 $N$ ($N \le 50$) 和$M$ ($M \le 20$)。

输出格式

对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0: 等)。

然后对应每个问题在一行中输出正整数 $N$ 的拆分方案数。

样例

Input
3
6 4
20 8
50 20
Output
case #0:
2
case #1:
13
case #2:
1969

307 人解决,336 人已尝试。

463 份提交通过,共有 639 份提交。

1.0 EMB 奖励。

创建: 6 年,5 月前.

修改: 2 年前.

最后提交: 4 天,18 小时前.

来源: 2014年编程实践课程第二次上机考试

题目标签