题目链接
题目概述
给出(N)个人,计算他们的可能的排名的数目,允许排名.比如三个人(P_1,P_2,P_3)它们之间可能的排名有(P_1 < P_2, P_2 < P_1, P_1 = P_2),总共有三种可能的排列顺序.
一点想法
首先为了简便考虑可以不使用(>),可以通过对称变换,改变人排列的顺序,将原始的(>)表示的变换为用(<)表示的,所以只需要考虑使用(<,=)着两种比较符号.
考虑没有(=)出现的情况,即这(N)个人没有出现平局,可以认为每个人组成一组,此时对这(N)个人进行全排列,然后向这(N)个人的(N-1)个空隙间隔中插入(<)有(N!)中方法.如果其中有两人的排名是相同的,那么认为这两个人构成一组,总共有(N-1)组,然后对这(N-1)组进行全排列,向其中插入(N-1-1)个(<).依次类推,当所有人的成绩都相同时,此时认为所有人组成一组.
于是可以将原问题转化为已知有(N)个小球,放到(k)个不同盒子的并且盒子不允许空的个数之和,这个可以通过第二类(Stirling)数简单变换来解决.第二类(Stirling)数(S(n,k))描述的是把(n)个不同的小球放入到(k)个相同的盒子并且盒子不空的数目.因为这里的盒子是带有标记的,即要在已知相同成绩的人数的情况下,将成绩相同的人看做一个整体与其它人一起进行一个全排列,对应着盒子是有区别带标记,需要在每一个(S(n,k))的基础上乘以一个(k!),这里的(k)表示的是因为排名相同看做一个组排名不同看做不同组而分成的组数.于是最终的答案就是:
[ans = sum_{k=1}^n{k!S(n,k)}
]
其它
第二类(Stirling)数也是有一个递推式的,用这个递推式可以较快的打表计算出结果.
[egin{aligned}
S(0,0) &= 0,S(k,0) = 0, S(k,k) = 1\
S(n,k) &= k * S(n-1, k) + S(n-1, k-1);
end{aligned}
]
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 105;
const int M = 20090126;
using ll = long long;
ll S[N][N];
ll F[N];
ll ans[N];
void calculate(){
S[0][0] = 1;
for (int i = 1; i < N; ++i){
S[i][i] = 1;
for (int j = 1; j < i; ++j){
// 第二类Sitriling数的递推式.
S[i][j] = (((j * S[i - 1][j]) % M) + (S[i - 1][j - 1] % M)) % M;
}
}
F[0] = 1;
for (int i = 1; i < N; i++) {
F[i] = ((F[i - 1] % M) * (i % M)) % M;
}
for (int i = 1; i < N; i++){
for (int j = 1; j <= i; j++){
ans[i] = ((ans[i] % M) + (((F[j] % M) * (S[i][j] % M)) % M)) % M;
}
}
}
int main(int argc, const char** argv){
calculate();
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
printf("%lld
", ans[n]);
}
}
2020年7月9日22:11:01