问一道ACM的题目

题目（ZOJ 1475）：
http://acm.zju.edu.cn/onlinejudge/showProblems.do?contestId=1&pageNumber=5

//------------------------------------------------------------

Ranklist

--------------------------------------------------------------------------------

Time Limit: 1 Second Memory Limit: 32768 KB

--------------------------------------------------------------------------------
If n people take part in this contest, how many distinct ranklists there could be? Notice that some contestants may share the same rank.

Input

One n on each line, the number of participants ( 1 <= n <= 200 ). A negative value for n indicates the end of input.

Output

One number on each line, the number of distinct ranklists.

Sample Input

1
2
3
-1

这题是dp+高精度, 递推式如下:

f(n) = g(n,1) + g(n,2) + ... + g(n,n)
其中, 又有 g(n,m) = g(n-1,m)*m + g(n-1,m-1)*m

f(n)表示n个人有多少种排列方法(即最终答案)
g(n,m)表示n个人m个rank有多少种排列方法

上面第一个式子非常好理解, 相信不用我讲了

第二个式子是重点:
1. 把g(n,m)对于其中某个人分类统计, 一是这个人与其他人共享rank, 二是这个人独占一个rank

2. 对于第一类, 这个人与其他人共享rank,
排列数为g(n-1,m)*m,
即先拿掉这个人, 其他人排一下m个rank, 为g(n-1,m), 然后这个人加入到m个rank中的某个里面去

3. 对于第二类, 这个人单独占一个rank(即没有其他人与这个人rank相同)
排列数为g(n-1,m-1)*m,
即先拿掉这个人, rank数也随之从m变为m-1, 其他人排一下, 为g(n-1,m-1), 然后这人插下队

式子大概是这样了, 计算时候注意一是要用高精度, 二是g(n,m)在m=1时, 等于1, 在m==n时, 等于n!, 其他时候, 等于那个递归式

看了半天也不知道这道题说的是什么。

帮忙翻译一道ACM的题目 新手，问ACM的一道题 java语言 ACM中一道简单的题目 ACM的一道题 帮忙解一道ACM竞赛题目 ACM 一道题目（高分求取） FPC的一道ACM题 一道ACM的简单题～ ACM的一道矩阵问题 c高手进 一道ACM的题目(改得好的话再送100分)