hdu2643&&hdu2512——斯特林数&&贝尔数

hdu2643

题意：$n$ 个人的排名情况数（$n \leq 100$）

分析：考虑 $n$ 个有区别的球放到 $m$ 个有区别的盒子里、无空盒的方案数为 $m!\cdot S(n, m)$。

这题中 $m$ 可取 $1 \sim n$（可能排名相同），累加即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = +;

const int mod = ;

int Sti[maxn][maxn], fact[maxn];  //第二类司特林数、贝尔数

void init()

{

    fact[] = ;

    for(int i = ;i < maxn;i++)  fact[i] = fact[i-] * i % mod;

    Sti[][] = ;

    for(int i = ;i < maxn;i++)

        for(int j = ;j <= i;j++)

            Sti[i][j] = (Sti[i-][j-] + 1LL * j * Sti[i-][j]) % mod;

}

int main()

{

    init();

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int n;

        scanf("%d", &n);

        int ans = ;

        for(int i = ;i <= n;i++) ans = (ans + 1LL * Sti[n][i] * fact[i]) % mod;

        printf("%d\n", ans);

    }

    return ;

}

hdu2512

题意：相当于求 $n$ 个元素的集合划分数（$1 \leq n \leq 2000$）

分析：即求第 $n$ 个贝尔数，$n$ 较小，直接用 $n^2$ 的暴力

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = +;

const int mod = ;

int Sti[maxn][maxn], bell[maxn];  //第二类司特林数、贝尔数

void Stirling2()

{

    Sti[][] = ;

    for(int i = ;i < maxn;i++)

        for(int j = ;j <= i;j++)

            Sti[i][j] = (Sti[i-][j-] + 1LL * j * Sti[i-][j]) % mod;

}

void init()

{

    Stirling2();

    bell[] = ;

    for(int i = ;i < maxn;i++)

        for(int j = ;j <= i;j++)

            bell[i] = (bell[i] + Sti[i][j]) % mod;

}

int  main()

{

    init();

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int x;

        scanf("%d", &x);

        printf("%d\n", bell[x]);

    }

    return ;

}

参考链接：https://www.cnblogs.com/xiaoxian1369/archive/2011/08/26/2154783.html

巴特西

hdu2643&&hdu2512——斯特林数&&贝尔数

最新文章

热门文章