大家好，又见面了，我是你们的朋友全栈君。
描述：
为解救可怜的武内崇老师，saber、远坂、爱尔奎特、希耶尔等人组成了第六科急救队！最终，由琥珀开发出了禁药，分身光线（这药是内服还是外用的= =？）,将爱尔奎特批量化生产，来对月世界进行全面的地毯式搜索。
现已知，第六科共有m个复制人（每个复制人完全一样），月世界有n个城市，每个城市会被一个复制人搜索一遍。问：共有多少种分配方法。（根据时空管理局劳务法更定，每个复制人又要分得工作。）
Input
每一行有一个m和n（1<=m<n<1000）
Output
每一行输出一个可能的个数（模10007取余）
Sample Input
2 4
1 5
Sample Output
7
1
解题思路：
这其实是求第二类斯特林数。{n,k}表示将有n件物品的集合划分成k个非空子集的方法数，显然{n,1}=1,{n,n} = 1,{n,0} = 0，并有以下递归式：
{n,k} = k{n-1,k}+{n-1,k-1}, n>0
解释：给定一个有n个元素的集合，要把它分成k个非空的部分，我们或者将最后元素单独放入一类（用{n-1,k-1}种方式），或者把它与前n-1个元素的某个非空子集放在一起。在后一种情况下，有k{n-1,k}种可能性，因为把前面n-1个元素分成k个非空部分{n-1,k}种方法的每一种都给出k个子集。
最后有一点要说明的是，虽然题目是n<1000，但实际提交发现其实是包括1000的，因为这种原因纠结了好长时间 。
#include <iostream>
using namespace std;
const int N = 1001;
int stirling[N][N];
int getStirling(int n,int k)
{
if(stirling[n][k]!=-1)
return stirling[n][k];
else
stirling[n][k] = (k*getStirling(n-1,k)+getStirling(n-1,k-1))%10007;
return stirling[n][k];
}
int main()
{
for(int i=0;i<N;++i)
for(int j=i;j<N;++j)
stirling[j][i] = -1;
for(int i=1;i<N;++i)
{
stirling[i][1] = 1;
stirling[i][i] = 1;
}
int m,n;
while(cin>>m>>n)
{
cout<<getStirling(n,m)<<endl;
}
return 0;
}
最后欢迎大家访问我的个人网站： 1024s
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/139033.html原文链接：https://javaforall.net
