HDU 2643 Rank：第二类Stirling数

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2643

题意：

　　有n个个选手参赛，问排名有多少种情况（可以并列）。

题解：

　　简化问题：

　　　　将n个不同的元素放到i个有差别的盒子中，情况数为P(n,i),求∑P(n,i)　(1<=i<=n)

　　再简化：

　　　　将n个不同的元素放到i个无差别的盒子中，情况数为S(n,i),求∑( S(n,i)*i! )　(1<=i<=n)

　　

　　哇这是第二类Stirling数 (￣▽￣)~*

　　递推式：s(n,k) = s(n-1,k-1) + k*s(n-1,k)

AC Code:

// s(n,k) = s(n-1,k-1) + k*s(n-1,k)
// s(n,n) = 1
// s(n,0) = 0
// ans = sigma(s[n][i = 1 to n] * i!)

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105
#define MOD 20090126

using namespace std;

int n,t;
long long s[MAX_N][MAX_N];
long long sum[MAX_N][MAX_N];
long long fact[MAX_N];

void stirling()
{
    memset(s,0,sizeof(s));
    for(int i=1;i<MAX_N;i++)
    {
        s[i][i]=1;
        for(int j=1;j<i;j++)
        {
            s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%MOD;
        }
    }
}

void cal_fact()
{
    fact[0]=1;
    for(int i=1;i<MAX_N;i++)
    {
        fact[i]=(fact[i-1]*i)%MOD;
    }
}

int main()
{
    stirling();
    cal_fact();
    cin>>t;
    for(int cas=1;cas<=t;cas++)
    {
        cin>>n;
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=s[n][i]*fact[i];
            sum%=MOD;
        }
        cout<<sum<<endl;
    }
}