MENU

HDU2643 Rank

HDU2643

第二类斯特林数:$n$个人放入$m$个非空集合的方案数。

$$S_{i,j}=S_{i-1,j-1}+S_{i-1,j} \times j$$

第$i$个人新开一个集合为$S_{i-1,j-1}$,放入现有集合为$S_{i-1,j} \times j$。


相同排名的人视为同一集合。即求放入$1 \cdots n$个集合的方案数,再乘上全排列。

$$\sum_{i=1}^nS_{n,i} \times i$$

#include<iostream>
using namespace std;
int T, n;
long long fac[101] = { 1 }, S[101][101];
int main() {
    for (int i = 1; i < 101; ++i) {
        fac[i] = fac[i - 1] * i % 20090126, S[i][1] = S[i][i] = 1;
        for (int j = 2; j < i; ++j)S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j) % 20090126;
    }
    ios::sync_with_stdio(0), cin.tie(0), cin >> T;
    while (T--) {
        cin >> n;
        long long ans = 0;
        for (int i = 1; i <= n; ++i)ans = (ans + (fac[i] * S[n][i] % 20090126)) % 20090126;
        cout << ans << '\n';
    }
}