Posted on 2009-09-09 12:55
Hero 閱讀(3293)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm
1 //HLOJ 1035 Accepted 0 196 469
2
3 //多重冪計數問題 -- catalan數
4
5 /*
6 Cn = (2*n)!
7 ------------
8 (n+1)!(n)!
9 */
10 #include <iostream>
11 using namespace std ;
12
13 int inn ;
14
15 unsigned __int64 Catalan( int n )
16 {
17 unsigned __int64 reval = 1 ;
18
19 int num[100] ;
20 memset( num, 0, sizeof(num) ) ;
21
22 for( int i=n+1; i<=2*n; i++ )
23 {
24 reval = reval * i ;
25 for( int j=2; j<=n+1; j++ )
26 {
27 if( 0 == num[j] && 0 == reval % j )
28 {
29 reval = reval / j ;
30 num[j] = 1 ;
31 }
32 }
33 }
34
35 return reval ;
36 }
37
38 int main()
39 {
40 while( cin >> inn )
41 {
42 cout << Catalan( inn-1 ) << endl ;
43 }
44
45 return 0 ;
46 }