这篇博客是从旧博客 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;
}
}