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

第二類斯特林?jǐn)?shù)：
第二類Stirling數(shù)實(shí)際上是集合的一個(gè)拆分，表示將n個(gè)不同的元素拆分成m個(gè)集合的方案數(shù)，記為 或者 。

第二類Stirling數(shù)的推導(dǎo)和第一類Stirling數(shù)類似，可以從定義出發(fā)考慮第n+1個(gè)元素的情況，假設(shè)要把n+1個(gè)元素分成m個(gè)集合則分析如下：
（1）如果n個(gè)元素構(gòu)成了m-1個(gè)集合，那么第n+1個(gè)元素單獨(dú)構(gòu)成一個(gè)集合。方案數(shù) 。
（2）如果n個(gè)元素已經(jīng)構(gòu)成了m個(gè)集合，將第n+1個(gè)元素插入到任意一個(gè)集合。方案數(shù) m*S(n,m) 。
　　綜合兩種情況得：
　　　　

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

思路：
這題就是求斯特林?jǐn)?shù)，即將n個(gè)隊(duì)伍分成i個(gè)集合(1 <= i <= n)。
然后對(duì)每個(gè)集合排序，乘上A(i,i)。也就是i !（i的階乘）。

代碼:

#include<cstdio> #include<cstring> #include<iostream> using namespace std;const int mod = 10056;int dp[1010][1010]; int main() { int t,n;cin >> t;int k = 1;while(t--){cin >> n;dp[0][0] = 1;for(int i = 1;i <= n; i++){for(int j = 1;j <= i; j++){dp[i][j] = (dp[i-1][j-1]+j*dp[i-1][j])%mod;}} int num = 1;int ans = 0;for(int j = 1;j <= n; j++){num = (num * j)%mod;ans = (ans + num*dp[n][j])%mod;}cout << "Case " << k++ << ": ";cout << ans << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的新疆大学（新大）OJ xju 1006: 比赛排名 第二类斯特林数+阶乘的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。