山东省第五届省赛 Hearthstone II

 发表于 April 21, 2015  |  2 分钟  |  275 个字  |  svtter

斯特林数stirling

  • 第一类 stirling数 s(n, k)

n个人分成k组，组内再按特定顺序围圈

也就是分成了k组，组内就像是项链颜色一样，

  1. ( {A, B}, {C, D} )
  2. ( {B, A}, {C, D} )

属于一组

  1. ({A}, {B, C, D})
  2. ({A}, {B, D, C})

不属于一组

给定 $s(n,0)=0,s(1,1)=1$，有递归关系$s(n,k)=s(n-1,k-1) + (n-1) s(n-1,k)$

  • 第二类 stirling数

S(n, k) 是把p元素集合划分到k个不可区分的盒子里且没有空盒的划分个数。

公式:

$$ S(n, n) = 1 (n >= 0) $$

$$ S(n, 0) = 0 (n >= 1) $$

$$ S(n,k)=k*S(n-1,k)+S(n-1,k-1),\text (1<=k<=n-1) $$

这样题目就好解决了。第五届省赛题目神经病。

因为每个桌子是不同的，所以还要利用乘法原理，$ans*m!$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数，内存处理
#define INF 0x3f3f3f3f
#define lln long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(b, -1, sizeof(b))
#define DEB(x, n) cout << (x) << " " << (n) << endl
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
#define mod 1000000007
const int maxn = 100 + 10;
lln s[maxn][maxn];
void init()
{
    for(int i = ; i < 101; i++) { s[i][] = ; s[i][i] = 1; }
    for(int n = 2; n < 101; n++)
        for(int k = 1; k <= n-1 ; k++)
            s[n][k] = ((k*s[n-1][k])%mod + s[n-1][k-1]%mod) %mod;
}
int readinput()
{
    int m, n;
    if(scanf("%d%d", &n, &m) == EOF)
        return ;
    else
    {
        lln ans = s[n][m];
        for(int i = 2; i <= m; i++)
        {
            ans *= i;
            ans %= mod;
        }
        printf("%lld\n", ans);
    }
    return 1;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    init();
    while(readinput());
    return ;
}