把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放， 问共有多少种不同的分法？5，1，1和1，5，1 是同一种分法。 输入 第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整 数M和N，以空格分开。1<=M，N<=10。 输出 对输入的每组数据M和N，用一行输出相应的K。 样例输入 1 7 3 样例输出 8

这是一道组合数学的问题，具体地说是求"从M个物品中取出N个物品的组合数"。公式如下：
C(M, N) = C(M, M-N) = M! / ((M-N)! * N!)

因此，在这个题目中，我们可以按照上面的公式来求出结果。

代码如下：

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

long long fac[21];

long long C(int m, int n)
{
    return fac[m] / fac[n] / fac[m-n];
}

int main()
{
    fac[0] = 1;
    for (int i = 1; i <= 20; i++)
        fac[i] = fac[i-1] * i;

    int t;
    cin >> t;
    while (t--)
    {
        int m, n;
        cin >> m >> n;
        cout << C(m, n) << endl;
    }

    return 0;
}

相关问题

把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分

如果允许有的盘子空着不放，这意味着每个盘子可以放0个或苹果个数的任意个数，总共有无数种分法。但是如果我们把空着不放的盘子排除在外，只考虑每个盘子至少放1个苹果的情况下，分法就有限制了。

我们可以用一种叫做"stars and bars"的方法来计算这个问题。假设每个盘子之间都有一个隔板来分隔苹果，前面的隔板表示前一个盘子放的苹果个数，最后一个隔板表示最后一个盘子剩下的苹果个数。例如，当m=3，n=2时，我们可以表示为：

★ | ★ ★ ｜ ☆ ☆

其中，★表示苹果，|表示隔板，☆表示空着不放的盘子。则第一个盘子放了1个苹果，第二个盘子放了2个苹果，第三个盘子空着不放。

而不同分法的种类数就等于将m个苹果和n-1个隔板排列在一起的不同排列数。即C(m+n-1,n-1) = (m+n-1)! / (n-1)!*m!。

所以，答案就是 C(m+n-1,n-1) = (m+n-1)! / (n-1)!*m! 种不同的分法。

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？

### 回答1：
这是一个经典的组合问题，求解的公式为：

C(m+n-1, n-1)

其中，C表示组合数，m表示苹果的个数，n表示盘子的个数。

具体解释如下：

将m个苹果放入n个盘子中，可以看作是将m个苹果分成n份的问题。我们可以用n-1个隔板将这m个苹果分成n份，每份至少有一个苹果。例如，将4个苹果分成3份，可以表示为：

* | ** * | ** * *

其中，*表示一个苹果，|表示一个隔板，左边的苹果分到第一个盘子中，中间的苹果分到第二个盘子中，右边的苹果分到第三个盘子中。

因此，将m个苹果分成n份的方案数，就等于将m个苹果和n-1个隔板排成一排的方案数，即：

C(m+n-1, n-1)

这就是答案。

### 回答2：
这道题目需要用到组合数学的知识来解决。我们可以假设有m个同样的苹果和n个同样的盘子，用x1, x2, ..., xn来代表每个盘子里放的苹果的个数，那么问题就转化为了如何找到所有满足下面条件的x1, x2, ..., xn的数量：

1. 每个xi都是非负整数
2. xi的和等于m

注意到没有对xi进行大小顺序的限制，所以这就是一个组合问题。我们可以用“插板法”来解决这个问题，即从m个苹果中选择n-1个位置来插n-1个板子，每个板子左边的苹果就对应放在一个盘子里的苹果个数。例如，在4个苹果，3个盘子的情况下，将苹果分开的分法可以表示为：

O | OO | O

其中“|”代表插板，左边的一堆1代表第一组放一个苹果的盘子，中间的一堆2代表第二组放两个苹果的盘子，右边的一堆1代表第三组放一个苹果的盘子。

因此，总共的分法数为C(m+n-1, n-1)，其中C代表组合数。此题的答案就是将m个苹果放入n个盘子中，允许盘子空着的方案数，所以本题的答案为C(m+n-1, n-1)。

### 回答3：
这道题需要我们运用组合数学的知识来解决。我们可以从小规模的情况开始推导，先考虑只有1个盘子的情况。此时我们只能把所有的苹果都放到这个盘子中，所以只有1种分法。

接下来考虑有2个盘子的情况。我们可以将所有的苹果都放在第一个盘子中，或者将苹果放在第二个盘子中，或者将苹果均分放在两个盘子中，因此有3种分法。

对于有3个盘子的情况，我们可以继续按照相似的思路来推导。假设第一个盘子有x个苹果，第二个盘子有y个苹果，第三个盘子有z个苹果。那么我们分别考虑这三种情况：

1. 第一个盘子有0个苹果，第二个盘子有0个苹果，第三个盘子有m个苹果，这种情况只有1种分法。

2. 第一个盘子有1个苹果，第二个盘子有0个苹果，第三个盘子有m-1个苹果。由于我们可以任意选择苹果放在第一个盘子中，因此有m种不同的放法。

3. 第一个盘子有x个苹果，第二个盘子有y个苹果，第三个盘子有z个苹果，且x+y+z=m。对于任意的分配方案，我们都可以通过将一个苹果从第一个盘子中挪到第二个盘子中，或者从第一个盘子中挪到第三个盘子中，或者从第二个盘子中挪到第三个盘子中，来得到新的方案。因此，对于这种情况，共有C(m-1,2)种不同的分法。

综上所述，有n个盘子时的分法总数应该是：

C(m+n-1,n-1) = (m+n-1)! / ((n-1)! * m!)

其中C表示组合数，m!表示m的阶乘。 例如，如果有4个苹果和3个盘子，不同的分配方案为：

1. 第一个盘子有0个苹果，第二个盘子有0个苹果，第三个盘子有4个苹果。

2. 第一个盘子有1个苹果，第二个盘子有0个苹果，第三个盘子有3个苹果。

3. 第一个盘子有2个苹果，第二个盘子有0个苹果，第三个盘子有2个苹果。

4. 第一个盘子有3个苹果，第二个盘子有0个苹果，第三个盘子有1个苹果。

5. 第一个盘子有4个苹果，第二个盘子有0个苹果，第三个盘子有0个苹果。

6. 第一个盘子有0个苹果，第二个盘子有1个苹果，第三个盘子有3个苹果。

7. 第一个盘子有1个苹果，第二个盘子有1个苹果，第三个盘子有2个苹果。

8. 第一个盘子有2个苹果，第二个盘子有1个苹果，第三个盘子有1个苹果。

9. 第一个盘子有3个苹果，第二个盘子有1个苹果，第三个盘子有0个苹果。

10. 第一个盘子有0个苹果，第二个盘子有2个苹果，第三个盘子有2个苹果。

11. 第一个盘子有1个苹果，第二个盘子有2个苹果，第三个盘子有1个苹果。

12. 第一个盘子有2个苹果，第二个盘子有2个苹果，第三个盘子有0个苹果。

13. 第一个盘子有0个苹果，第二个盘子有3个苹果，第三个盘子有1个苹果。

14. 第一个盘子有1个苹果，第二个盘子有3个苹果，第三个盘子有0个苹果。

因此，总共有14种不同的分法。