HDOJ 1465 不容易系列之一 【错排公式 递推】
题目就是说n个信封全部装错信的可能性是多少
可以使用欧拉全错排公式：f(n)=n![1/2!-1/3!+1/4!+…+(-1)^n*1/n!] (n>1)
可以参考这个链接
http://wenku.baidu.com/link?url=sVYQBg1nPE0xGWHLNTjSUbmLkPk2IM9Dvp4Md-c_yOLTlHlYj1SiblJ-rAND_4mEhSi6qWKDPlv_24ypXAXflPGMi8A32K7IYaMVCDZ4BIG
也可以使用递推公式
从上一个状态转移到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<cstdio> 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 ", f[n]); 12 return 0; 13 }
版权声明：本文为博主原创文章，未经博主允许不得转载。