XDOJ1145–组合数学四之Carnival Phantasm

XDOJ1145–组合数学四之Carnival Phantasm描述:为解救可怜的武内崇老师,saber、远坂、爱尔奎特、希耶尔等人组成了第六科急救队!最终,由琥珀开发出了禁药,分身光线(这药是内服还是外用的==?),将爱尔奎特批量化生产,来对月世界进行全面的地毯式搜索。现已知,第六科共有m个复制人(每个复制人完全一样),月世界有n个城市,每个城市会被一个复制人搜索一遍。问:共有多少种分配方法。(根据时空管理局劳务法更定,每个复制人又要分得工作。)…

大家好,又见面了,我是你们的朋友全栈君。

描述:

为解救可怜的武内崇老师,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账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号