HDU/HDOJ 2512 一卡通大冒险

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2512

斯特林数,组合数学的知识。

斯特林数:

斯特林数出现在许多组合枚举问题中. 对第一类斯特林数 StirlingS1[n,m], 给出恰包含 m 个圈的 n 个元素 的排列数目. 斯特林数满足母函数关系 . 注意某些 的定义与 Mathematica 中的不同,差别在于因子 . 第二类斯特林数 StirlingS2[n,m]给出把 n 个可区分小球分配到m个不可区分的的盒子,且盒子没有空盒子的方法的数量. 它们满足关系 . 划分函数 PartitionsP[n]给出把整数 n 写为正整数的和,不考虑顺序的方法的数目. PartitionsQ[n]给出把整数 n 写为正整数的和,并且和中的整数是互不相同的 写法的数目

递推,设a[i][j]为i张卡放j本书且每本书有卡的方法数,则a[i][j] = j * a[i – 1][j] + a[i – 1][j – 1];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
using namespace std;
 
int a[2005][2005];
 
int main()
{
    a[1][1] = 1;
    a[2][1] = 1;
    a[2][2] = 1;
    a[3][1] = 1;
    a[3][2] = 3;
    a[3][3] = 1;
    for(int i=4; i<=2000; ++i)
    {
        a[i][1] = 1;
        a[i][i] = 1;
    }
    for(int i=4; i<=2000; ++i)
        for(int j=2; j<=2000; ++j)
            a[i][j] = (j*a[i-1][j] + a[i-1][j-1])%1000;
    int n;
    cin >> n;
    int t;
    while(n--)
    {
        cin >> t;
        int tmp = 0;
        for(int i=1; i<=t; ++i)
        {
            tmp += a[t][i];
            tmp %= 1000;
        }
        cout << tmp << endl;
    }
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 2512 一卡通大冒险》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注