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)


相关推荐

  • 博客园现代化建设——Entity Framework

    博客园现代化建设——Entity Framework

  • hashmap线程不安全问题_arraylist线程不安全体现在哪里

    hashmap线程不安全问题_arraylist线程不安全体现在哪里一、头插法导致死循环在jdk1.7以前,HashMap在进行扩容时采用的是头插法,可能当时别人觉得这样比较高效,但是也带来了线程安全问题。刚开始时HashMap是这样的:正常扩容后是这样的:但如果是在多线程下,两个线程的指向3:此时线程1比线程2先执行,那么线程1就会指向7,将线程7.next指向了3,:但是对于线程2来说,3.next=7;所以就形成了死循环,也就是3和7构成了环。二、数据覆盖在jdk1.8以后,改了1.7以前的小毛病,但是新的问题又来了,我们来看下源码:

  • 支持向量机的原理

    一、什么是支持向量机  支持向量机(supportvectormachine,简称SVM)是一种基于统计学习理论的新型学习机,是由前苏联教授Vapnik最早提出的。与传统的学习方法不同,支持向量机是结构风险最小化方法的近似实现。这个归纳原理是基于这样的事实,学习机器在测试数据上的误差率(即泛化误差率)以训练误差率和一个依赖于Vc维数(Vapnik-Chervonenkisdimensio…

  • Python:Python学习总结

    Python:Python学习总结背景PHP的$和->让人输入的手疼(PHP确实非常简洁和强大,适合WEB编程),Ruby的#、@、@@也好不到哪里(OO人员最该学习的一门语言)。Python应该是写起来最舒服的动态语言了,一下

  • 微服务架构(java环境&tomcat)

    微服务架构(java环境&tomcat)

  • 最良心的csgo开箱网站_csgo靠谱交易平台

    最良心的csgo开箱网站_csgo靠谱交易平台2021csgo网页开箱网站有哪些?csgo靠谱的开箱网站大全官网直达链接优惠码/推广码网站状态incsgocsgogo直接取回skinsdogcsgogo直接取回88skinscsgo直接取回skskinscsgogo直接取回npskinscsgogo直接取回fateskinscsgo直接取回yskins暂无可取回coolkaixiangcsgo直接取回piggycasecsgogo可取回bo

发表回复

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

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