这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1465
思路:
传说中的“错排公式”=。=
当有n封信时,前n-1封或前n-2封可能错。
如果前n-1封错,则可以把第n封与前面任意n-1封交换而使n封全错。有f(n-1)*(n-1)
如果前n-2封错,则可以把对的那封与第n封交换,而对的那封可以是n-1封内任意一封。所以有f(n-2)*(n-1)
所以 f(n) = (f(n-1)+f(n-2)) * (n-1)
代码:
// Author: Tanky Woo
// HDOJ 1465
#include
using namespace std;
__int64 f[22];
int main()
{
f[1] = 0;
f[2] = 1;
f[3] = 2;
for(int i = 4; i <= 20; ++i)
f[i] = (i-1)*(f[i-2]+f[i-1]);
int num;
while(scanf("%d", #) != EOF)
//是说用__int64没效果,原来输出时忘了加%I64d
printf("%I64d\n", f[num]);
return 0;
}