hdu1465 参考答案

   1 /*
   2 1465 不容易系列之一，递推求解
   3 ymc 2008/9/23
   4 题目大意：
   5 有n封信和n个信封，求所有的信都装错信封,共有多少种不同情况。
   6 分析与解题思路：
   7 称n封信与n个信封，所有信装错信封的个数为n错排数。
   8 设F[n]为n错排数，设
   9 a1,a2,,,.an为1,2,...n的一个错排。
  10 则找到n所在的数，假设为ai，交换ai与an，得到
  11 a1,a2,,an,..an-1,ai=n
  12 前面的n-1个数a1,a2,..an,..an-1有两种情况
  13 1）为n-1错排数，总共有F[n-1]种，
  14 2）an没有错排，剩下的n-2个数错排。则有F[n-2]种。
  15 又ai有n-1种可能。则
  16 F[n]=(F[n-1]+F[n-2])*(n-1)
  17 注意：用int会溢出
  18 */
  19 #include <iostream>
  20 using namespace std;
  21 const int N=21;
  22 long long  F[N];
  23 void Init()
  24 {
  25     F[1]=0;
  26     F[2]=1;
  27     for(int i=3;i<N;i++)
  28         F[i]=(F[i-1]+F[i-2])*(i-1);
  29 }
  30 int main()
  31 {
  32     int n;
  33     Init();
  34     while(cin>>n)
  35     {
  36         cout<<F[n]<<endl;
  37     }
  38 }