SDUT2883 Hearthstone II(第二类Stiring数)

2014年山东省第五届ACM省赛

Posted by Scalpel on May 13, 2016

题目链接

题意:

要举行n场比赛,需要m个桌台,每场比赛可以分配任意个桌台,每个桌台至少用一次,求有多少种分配方案

思路:

  这里简要介绍一下Stiring数参考资料

一.第二类Stirling数

  定理:第二类Stirling数计数的是把p元素集合划分到k个不可区分的盒子里且没有空盒子的划分个数。
  证明:元素在拿些盒子并不重要,唯一重要的是各个盒子里装的是什么,而不管哪个盒子装了什么。
  递推公式有:
  
  
  
  考虑将前p个正整数的集合作为要被划分的集合,把分到k个非空且不可区分的盒子的划分有两种情况:(1)那些使得p自己单独在一个盒子的划分,存在有种划分个数;(2)那些使得p不单独自己在一个盒子的划分,存在有种划分个数。
  考虑第二种情况,p不单独自己在一个盒子,也就是p和其他元素在一个集合里面,也就是说在没有放p之前,有p-1个元素已经分到了k个非空且不可区分的盒子里面(划分个数为,那么现在问题是把p放在哪个盒子里面呢,有k种选择,所以存在有

二.Bell数

  定理:Bell数是将p元素集合分到非空且不可区分盒子的划分个数(没有说分到几个盒子里面)。所以要求Bell数就要先求出第二类Stiring数。

三.第一类Stirling数

  定理:第一类Stirling数计数的是把p个对象排成k个非空循环排列的方法数。
  证明:把上述定理叙述中的循环排列叫做圆圈。递推公式为:
  (有p个人和p个圆圈,每个圆圈就只有一个人)
  (如果至少有1个人,那么任何的安排都至少包含一个圆圈)
  
  设人被标上。将这p个人排成k个圆圈有两种情况。第一种排法是在一个圆圈里只有标号为p的人自己,排法有个。第二种排法中,p至少和另一个人在一个圆圈里。这些排法可以通过把排成k个圆圈再把p放在任何一人的左边得到,因此第二种类型的排法共有种排法。
  在证明中我们所做的就是把划分到k个非空且不可区分的盒子,然后将每个盒子中的元素排成一个循环排列。

题解:

  第二类Stiring数,由于桌台是可区分的,所以答案为

#include <iostream>   
#include <cstdio>   
using namespace std;  
  
#define FIO ios_base::sync_with_stdio(false); cin.tie(0);  
#define FILEREAD freopen("input.txt", "r", stdin);  

const int N = 101;  
long long s[N][N] = {0};  
int main()  
{  
#ifndef ONLINE_JUDGE  
    FILEREAD  
#endif  
    FIO      
    s[1][1] = 1;  
    for (int i = 2; i <= 100; ++i)  
        for (int j = 1; j <= i; ++j)  
            s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % MOD;  
    int n, m;  
    while (cin >> n >> m)  
    {  
        long long ans = s[n][m];  
        for (long long i = 2; i <= m; ++i)  
            ans = (ans * i) % MOD;  
        cout << ans << endl;  
    }  
    return 0;  
}