分析
n个数放入m个集合,要求每个集合非空。
f[i][j]表示前i个数方入j个集合的方案总数。
分两种情况:
1.第i个数放入新的集合,则有f[i-1][j-1]种方案
2.第i个数放入原来的集合中的一个,总的集合数不变,则一共有jf[i-1][j]中方案
两种情况加起来就是总情况个数:f[i][j]=f[i-1][j-1]+jf[i-1][j]
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010,mod = 1e9+7;
typedef long long LL;
int f[N][N];
int n,m;
int main()
{
cin>>n>>m;
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=(f[i-1][j-1]+(LL)j*f[i-1][j])%mod;
}
}
cout<<f[n][m]<<endl;
return 0;
}