总时间限制: 1000ms 内存限制: 65536kB

描述

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入

第一行是测试数据的数目t（0 ≤ t ≤ 20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。

输出

对输入的每组数据M和N，用一行输出相应的K。

样例输入

1
7 3

样例输出

8

思路

这里要用到分类讨论的数学思想和排列组合的数学知识:

设 apple 个苹果放在 plate 个盘子里的放法总数是 f(apple, plate), 则:

• plate > apple 时, f(apple, plate) = f(apple, apple)
  因为我们把 (palte - apple) 个盘子拨到一边, 只考虑 apple 个盘子放 apple 个苹果.

• plate ≤ apple 时, 总放法 = 有盘子为空的放置 + 没有盘子为空的放法.

  1. 有盘子为空的集合，该集合至少有一个盘子是被拿走的. 所以该集合的方法等于 f(apple, plate - 1).
  2. 盘子不为空的集合，分2步走. 第一步, 把 (apple - plate) 个苹果放到 plate 个盘子里, 这样就确保了每个盘子都有苹果了; 第二步, 把剩下的苹果按照组合的方法放进盘子里.

%20%3D%20f(apple%2C%20plate%20-%201)%20%2B%20f(apple%20-%20plate%2C%20plate)%0A#card=math&code=f%28apple%2C%20plate%29%20%3D%20f%28apple%2C%20plate%20-%201%29%20%2B%20f%28apple%20-%20plate%2C%20plate%29%0A)

• 边界条件为：

代码

#include <iostream>
using namespace std;
int function(int apple, int plate) {
    if(plate > apple)  // 有盘子为空的情况
        return function(apple, apple);
    if( apple == 0 )  // 边界条件1
        return 1;
    if( plate == 0 )  // 边界条件2
        return 0;
    return function(apple, plate - 1) + function(apple - plate, plate);
}
int main() {
    int number, apple, plate;
    cin >> number;
    while( number-- ) {
        cin >> apple >> plate;
        cout << function(apple, plate) << endl;
    }
    return 0;
}