HDOJ 1465 不容易系列之一 【错排公式 递推】

题目链接

---

题目就是说n个信封全部装错信的可能性是多少

可以使用欧拉全错排公式：f(n)=n![1/2!-1/3!+1/4!+…+(-1)^n*1/n!] (n>1)

可以参考这个链接

---

也可以使用递推公式

从上一个状态转移到n封信全错只有两种可能：

1、前面n-1封信全错，第n封从前面挑选一个位置交换即全错，f(n-1)*(n-1)

2、前面n-2封信全错，第n封和没放错的那个位置交换即全错，f(n-2)*(n-1) （n-1是挑选没有放错的位置的可能性）

其他的可能情况都不能在一步之后达到n封全错的状态

得到递推公式：f(n) = ( f(n-1) + f(n-2) ) * (n-1)

---

1 #include
      
        2 int n; 3 long long f[25]; 4 void Pre(){ 5     f[1] = 0, f[2] = 1; 6     for(int i = 3; i <= 20; i++) f[i] = (f[i-1] + f[i-2]) * (i-1); 7 } 8  9 int main(){10     Pre();11     while(~scanf("%d", &n)) printf("%I64d\n", f[n]);12     return 0;13 }
      

 

版权声明：本文为博主原创文章，未经博主允许不得转载。