1011.盒子与球 SDNUOJ1011

Description
现有r个互不相同的盒子和n个互不相同的球，要将这n个球放入r个盒子中，且不允许有空盒子。则有多少种放法？
Input
n, r(0 <= n, r <= 10)。
Output
有多少种放法。
Sample Input
3 2
Sample Output
6

第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数。描述为：将n个不同的球放入m个无差别的盒子中，要求盒子非空，有几种方案？

递推式
第二类Stirling数的推导和第一类Stirling数类似，可以从定义出发考虑第n+1个元素的情况，假设要把n+1个元素分成m个集合则分析如下：
（1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数 。
（2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 m*S(n,m) 。
综合两种情况得：

#include <iostream>
using namespace std;

int fac(int n)
{
    int a = 1;
    while( n > 0 )
    {
        a *= n;
        n--;
    }
    return a;
}

int main()
{
    int m, n;
    long long f[11][11] = { 0 };
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
        f[i][i]=1;
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= m; j++)
            f[i][j] = f[i - 1][j - 1] + i * f[i][j - 1];
    cout << fac(n) * f[n][m] << '\n';
    return 0;
}