HOJ 2643 Rank（第二类斯特林数，裸题）

第二类斯特林数，裸题
题目意思：
给出n个人,计算他们的可能的排名的数目. 学生x 和 y 的关系有三种，x > y, x == y, x < y;

本题要点：
1、第二类斯特林数，定义：
把n个不同相同的元素，放到k个相同的集合，不允许集合为空。 一共有 s2(n, k) 中放法。
2、n个学生，可能有 m 个不同的分数, m 的取值范围是 1 <= m <= n;
n个学生，放到 m个不同集合里面，有 s2(n, m) 种放法。但是这m个集合的顺序不同的话，视作不同的排名。
因此，m种分数的话，一共有 s2(n, m) * m! 种。
m 从 1 到 m 全部相加即可。
3、 参考 https://blog.csdn.net/u011815404/article/details/80083954

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int MaxN = 110;
const ll mod = 20090126;
ll s[MaxN][MaxN];	//斯特林数
ll fac[MaxN];
int T, n;void init()
{
    memset(s, 0, sizeof s);s[1][1] = 1;for(int i = 2; i < MaxN; ++i){
    for(int j = 1; j <= i; ++j){
    s[i][j] = (s[i - 1][j - 1] % mod + j * s[i - 1][j] % mod) % mod;}}fac[0] = fac[1] = 1;for(int i = 2; i < MaxN; ++i){
    fac[i] = fac[i - 1] * i % mod; }
}void solve()
{
    ll res = 0;for(int i = 1; i <= n; ++i){
    res = (res + s[n][i] * fac[i]) % mod;}printf("%lld\n", res);
}int main()
{
    init();scanf("%d", &T);while(T--){
    scanf("%d", &n);solve();}return 0;
}/* 2 2 3 *//* 3 13 */