Blog·Tanky WooABOUTRSS

HDU/HDOJ 2512 一卡通大冒险

18 Jan 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

传送门: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];

#include 
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;
    }
}