大家好,又见面了,我是你们的朋友全栈君。
描述:
为解救可怜的武内崇老师,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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/139033.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...