新疆大学（新大）OJ xju 1006: 比赛排名 第二类斯特林数+阶乘

题目链接：http://acm.xju.edu.cn/JudgeOnline/problem.php?id=1006

第二类斯特林数：

第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数，记为  或者 。

第二类Stirling数的推导和第一类Stirling数类似，可以从定义出发考虑第n+1个元素的情况，假设要把n+1个元素分成m个集合则分析如下：

（1）如果n个元素构成了m-1个集合，那么第n+1个元素单独构成一个集合。方案数 。

（2）如果n个元素已经构成了m个集合，将第n+1个元素插入到任意一个集合。方案数 m*S(n,m) 。

　　综合两种情况得：

　　　　

 

 

递推式：dp[i][j] = dp[i-1][j-1]+j*dp[i-1][j]；

 

 

 

 

思路：

这题就是求斯特林数，即将n个队伍分成i个集合(1 <= i <= n)。

然后对每个集合排序，乘上A(i,i)。也就是i !（i的阶乘）。

 

 

 

 

代码:

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int mod = ;

int dp[][];

int main()  {

  int t,n;

  cin >> t;

  int k = ;

  while(t--){

      cin >> n;

      dp[][] = ;

        for(int i = ;i <= n; i++){

            for(int j = ;j <= i; j++){

                    dp[i][j] = (dp[i-][j-]+j*dp[i-][j])%mod;

            }

        }

        int num = ;

        int ans = ;

        for(int j = ;j <= n; j++){

            num = (num * j)%mod;

            ans = (ans + num*dp[n][j])%mod;

        }

        cout << "Case " << k++ << ": ";

        cout << ans << endl;

    }

  return ;

}