Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:闲来无事我也贴一个证明……LANGUAGE: C++ TIME:16ms

Posted by 768059009 at 2017-04-28 23:11:12 on Problem 1354
In Reply To:闲来无事我也贴一个证明……LANGUAGE: C++ TIME:16ms Posted by:Ruby931031 at 2012-09-12 22:59:26
> //能解开所有盒子的情况分为两类:
> //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;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator