ACM_数数有多少（第二类Stirling数-递推dp）

数数有多少

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

小财最近新开了一家公司，招了n个员工，但是因为资金问题，办公楼只有m间办公室，于是小财找到了作为程序员的你解决一个问题:将这n个不同的员工安排在m间相同的办公室(即办公室不可区分)一共有多少种方式?其中每间办公室可以安排任意个数的雇员(包括空办公室).

Input:

输入有多组数据
每组数据输入两个数n m (0<m<=n<=100)

Output:

输出安排的方式数（由于答案较大,最终输出答案对1000007取模）

Sample Input:

4 3

Sample Output:

14

hint:
对于样例有以下几种方式:
1、把4个员工分到一间办公室，1种
2、将3个员工安排在同一间办公室，第4个员工安排在另一间办公室，4种
3、将2个员工安排在同一间办公室，另外2个员工安排在另一间办公室，3种
4、将2个员工安排在同一间办公室，另外2个员工各自安排在不同的办公室，6种
所以1+4+3+6=14种
解题思路：第二类斯特林数：把n个元素划分成m个无序集合的方案数。递推一下公式：dp[i][j]表示i个元素分成j个集合的方案数。①如果i-1个元素已经构成了j-1个集合，那么第i个元素单独构成一个集合的方案数为dp[i-1][j-1]*1（空的集合都是无序相同的，任选一个即可）；②如果i-1个元素已经构成了j个集合，将第i个元素插入到任一个集合中的方案数为dp[i-1][j]*j（选择j个集合中的一个有j种选法）。所以i个元素构成j个集合的总方案数为dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j。对于这道题，思路基本一样，简单套一下递推公式即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int mod=1000007;
typedef long long LL;
LL ans,dp[maxn][maxn];int n,m;
int main(){//第二类斯特林数
    while(cin>>n>>m){
        memset(dp,0,sizeof(dp));ans=0;//清0
        for(int i=1;i<=n;++i)dp[i][1]=1;//将i个员工分到一间办公室有1种分法
        for(int i=2;i<=n;++i)//从两个员工开始枚举，因为一个员工的情况已计算过了：dp[1][1]=1;
            for(int j=2;j<=i;++j)//从两间办公室开始枚举，因为i个员工分配到一间办公室的情况已计算过了：1种，i个员工最多分配到i间办公室，所以j只需枚举到i即可
                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)%mod;
        for(int i=1;i<=m;++i)ans+=dp[n][i];//累加n个员工分配到i（i∈[1,m]）间办公室的所有情况数
        cout<<ans%mod<<endl;//最后取个模
    }
    return 0;
}