题目大意:n个盒子对应n个锁,n个锁对应着唯一可以打开它的n把钥匙,现将n把钥匙封于n个盒
子中,只撬开1 2两个盒子,不能再撬开其他盒子,用已撬开或者打开的盒子内的钥匙来开别的盒
子,问能够最终打开所有盒子的钥匙的放置方法有多少种。
题目分析:
这题是一个错排问题,就是在排列中不存在恰好i1,i2,i3,...,ik包含i1,i2,i3,...,ik号钥匙的情
况(不一定一一对应,只要恰好包含即可)k<n,这题用传统的错排推公式是可以完成的,但是比
较
复杂,我们可以设以1和2中一个点为起始点依次打开所有盒子,形成一个环,那么我们可以把1 2
放置于环上的任意位置上,即n*(n-1),但是环上无绝对位置,所以最终为n-1种,然后剩下n-2全
排列,所以为(n-1)!
当然1和2也可以独自成环,环的大小即解x+y=n的正整数解方程,n-1个解,剩下的n-2个数可以全
排列,作为环上顺序,所以为(n-1)*(n-2)!,所以为(n-1)!,即结果为2*(n-1)!
这题范围比较大,要用高精度
#include<iostream> #include<cstdio> using namespace std; int arr[10000]; void factorial(int n)//求阶乘 { memset(arr,0,sizeof(arr)); arr[1]=2; int c=1,temp,temp1; for(int i=2;i<=n;i++) { temp=0; for(int j=1;j<=c;j++) { temp1=arr[j]*i+temp; arr[j]=temp1%10; temp=temp1/10; } while(temp!=0)// { arr[++c]=temp%10; temp/=10; } } for(int i=c;i>=1;i--) printf("%d",arr[i]); printf("\n"); } int main() { int n; while(scanf("%d",&n)!=EOF&&n!=0) { printf("N=%d:\n",n); factorial(n-1); } //system("pause"); return 0; }