//能解开所有盒子的情况分为两类：
//A>   用盒子1里的钥匙去开它对应的锁a_1,再用盒子a_1里的钥匙去开它对应的锁a_2，等等，依次类推。其中某一个a_s恰好是2号盒子
//这样一来就构成了一个环：1-> a_1 -> a_2 -> .. -> a_s-1 -> a_s=2 -> a_s+1 -> .. -> a_n-1
//也即，事实上只需一把钥匙就能打开所有的锁。此时盒子里放钥匙的方案就是(n-1)!种（后面n-1个位置由2到n进行全排列）

//B>   必须用两把钥匙才能打开所有的盒子，也即，每把钥匙能打开的锁各自构成了一个环，共两个环；
//设两个环的大小分别为x和y，则有x+y=n。每组解对应的放置方案可以写为两条链:
//1 -> a1 -> a2 -> .. -> a(x-1)  ,  2 -> b1 -> b2 -> .. -> b(y-1)
//前一条链表示盒子1放a1, 盒子a2放a3, .. ,盒子a(x-1)放1,在a1,a2,..,a(x-1)取定后共(x-1)!种可能;
//后一条链同理,在b1,b2,..,b(y-1)取定后共(y-1)!种可能
//故可分为两条链的放置方案总数为：
//Sigma( C(n-2, x-1)*(x-1)!*(y-1)! )
//(Sigma是对x+y=n且x,y均为正整数求和，前面乘一个组合数是选定哪些数在链1、哪些数在链2上)
//对此式求和后可知化简后为(n-1)!

//由加法原理知，总的方案数为：(n-1)! + (n-1)! = 2(n-1)!

#include <stdio.h>
#define MAXN 205
#define MAXM 1050
#define BASE 10000
int res[MAXN][MAXM]={0},msb[MAXN]={0}; //2*(i-1)!保存在res[i][]中，msb[i]为2*(i-1)!最高位的位置

int main(){
	int n,i,j;
	res[3][0]=4;
	msb[3]=0;
	for (i=3; i<MAXN-2; ++i){
		for (j=0; j<=msb[i]; ++j){
			res[i+1][j] += res[i][j]*i;
			res[i+1][j+1] += res[i+1][j]/BASE;
			res[i+1][j] %= BASE;
		}
		if (res[i+1][msb[i]+1])		msb[i+1]=msb[i]+1;
		else	msb[i+1]=msb[i];
	}

	while (scanf("%d", &n)!=EOF && n!=-1){
		printf("N=%d:\n%d", n, res[n][msb[n]]);
		for (i=msb[n]-1; i>=0; --i)
			printf("%04d", res[n][i]);
		printf("\n");
	}

	return 0;
}

• Re:闲来无事我也贴一个证明……LANGUAGE: C++ TIME:16ms (1423) 768059009 2017-04-28 23:11:12