Stirling数

Stirling数"/>

Stirling数

第一类Stirling数

定义第一类Stirling数是s(n,k)：把n个不同否元素分配到k个圆排列里，圆不能为空，有多少种分法？

递推公式：s(n,k) = s(n - 1,k - 1) + (n - 1)s(n - 1,k),1<=k<=n;

                s(0 , 0)=0;s(k,0)=1,1<=k<=n;

第二类Stirling数

定义：把n个不同的球分配到k个相同的盒子里，不能有空盒子，多少种分法。

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

                    s(0 , 0)=1; s(i,0)=0, 1<=k<=n;

例题：

HDU4372(第一类斯特林数)

题意：N座高楼，高度均不同且为1~N中的数，从前向后看能看到F个，从后向前看能看到B个，问有多少种可能的排列数。

0 < N, F, B <= 2000

首先我们知道一个结论：n的环排列的个数与n-1个元素的排列的个数相等，因为P(n,n)/n=(n-1)!。

可以肯定，无论从最左边还是从最右边看，最高的那个楼一定是可以看到的.

假设最高的楼的位置固定，最高楼的编号为n，那么我们为了满足条件，可以在楼n的左边分x-1组，右边分y-1组，且用每

组最高的那个元素代表这一组，那么楼n的左边，从左到右，组与组之间最高的元素一定是单调递增的，且每组中的最高元

素一定排在该组的最左边，每组中的其它元素可以任意排列（相当于这个组中所有元素的环排列）。右边反之亦然。

然后，可以这样考虑这个问题，最高的那个楼左边一定有x-1个组，右边一定有y-1个组，且每组是一个环排列，这就引出

了第一类Stirling数（个人分成组，每组内再按特定顺序围圈的分组方法的数目）。

我们可以先把n-1个元素分成x-1+y-1组，然后每组内部做环排列。再在所有组中选取x-1组放到楼n的左边。所以答案是

ans(n, f, b) = C[f + b - 2][f - 1] * S[n - 1][f + b - 2];
 

#include <iostream>
#include <string.h>
#include <stdio.h>using namespace std;
typedef long long LL;const int N=2005;
const LL MOD=1000000007;LL C[N][N];
LL S[N][N];void Init()
{int i,j;for(i=0;i<N;i++){C[i][0]=1;C[i][i]=1;S[i][0]=0;S[i][i]=1;for(j=1;j<i;j++){C[i][j]=(C[i-1][j]%MOD+C[i-1][j-1]%MOD)%MOD;S[i][j]=((i-1)%MOD*S[i-1][j]%MOD+S[i-1][j-1]%MOD);}}
}int main()
{LL t,n,f,b,ans;Init();scanf("%I64d",&t);while(t--){scanf("%I64d%I64d%I64d",&n,&f,&b);ans=C[f+b-2][f-1]%MOD*S[n-1][f+b-2]%MOD;//数组c表示从这么多楼中选出x-1幢，数组s表示排列printf("%I64d\n",ans);}return 0;
}

HDU_2643_Rank

最近在泰迪的家乡有一个叫“牛年吹牛”的比赛，N名选手参加了这次比赛，比赛非常激烈，排名不断变化。

现在的问题是：

n个竞争者在一场比赛中能以多少种不同的方式排名，考虑到结盟的可能性。

由于答案将非常大，您可以只输出答案mod 20090126。

Problem Description
Recently in Teddy's hometown there is a competition named "Cow Year Blow Cow".N competitors had took part in this competition.The competition was so intense that the rank was changing and changing.
Now the question is:
How many different ways that n competitors can rank in a competition, allowing for the possibility of ties. 
as the answer will be very large,you can just output the answer MOD 20090126.
Here are the ways when N = 2:
P1 < P2
P2 < P1
P1 = P2 
 

Input
The first line will contain a T,then T cases followed.
each case only contain one integer N (N <= 100),indicating the number of people.
 

Output
One integer pey line represent the answer MOD 20090126.
 

Sample Input
2 2 3
 

Sample Output
3 13
 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=110;
const int mod=20090126;
LL dp[maxn][maxn],f[maxn];
void Init(int n){dp[0][0]=1;f[0]=1;for(int i=1;i<=n;i++){f[i]=i*f[i-1]%mod;//每个组合看成数字1，2，3，4，数字有多少中排列for(int j=1;j<=i;j++)dp[i][j]=((j%mod*dp[i-1][j]%mod)%mod+dp[i-1][j-1]%mod)%mod;//第二类公式}
}
int main()
{int t,n;Init(100);scanf("%d",&t);while(t--){LL ans=0;scanf("%d",&n);for(int i=1;i<=n;i++)ans=(ans+dp[n][i]*f[i])%mod;printf("%I64d\n",ans);}return 0;
}