ZJU/ZOJ 1619 Present 解题报告

题目大意是有n个人各自买了一份礼物，打乱放在一起，每个人拿一份带走，问恰好有m个人拿回了自己那份礼物的几率是多少。

很明显的组合数学问题，题目所求的情况数实际就是c(n,m)*(n-m)的错排数。化简可得这样一条通项公式：∑((-1)^i/i!)/m!(2<=i<=n-m)。不过我没推出求∑((-1)^i/i!)的递推式，所以还是用了朴素的方法c(n,m)*(n-m)的错排数/n的全排列数，化简可得(n-m)的错排数/((n-m)!*m!)。可以做两个预处理优化，预先求出0到99的阶乘和错排数，用到时直接调用计算即可。

用f(n)表示n的错排数，求f(n)除了可以通过由容斥原理得到的f(n)的通项公式f(n)=n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]来求外，还可以通过递推来求。显然将任一位置的元素错排都有n-1种方法（将其插入到不同于自己位置的其它元素位置），假设第一个选取的元素为第i个位置的元素，将其插入第k个位置。我们可以分两种情况来考虑，假设第k个位置的元素插入到第i个位置，则实际上是对剩下的n-2个元素进行错排；假设第k个位置的元素不插入第i个位置，则实际上是对剩下的n-1个元素进行错排。根据乘法原理f(n)=(n-1)*(f(n-1)+f(n-2))。显然通过递推的方法来求错排数，无论是编程复杂度还是时间复杂度都优于用通项公式来求。

3018896 2008-08-02 22:24:15 Accepted 1619 FPC 00:00.01 416K IwfWcf@LZOI