HDU 2200 Eddy's AC難題（組合數學）

Eddy's AC難題

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 5107    Accepted Submission(s): 2399

Problem Description

Eddy是個ACMer,他不僅喜歡做ACM題,而且對于Ranklist中每個人的ac數量也有一定的研究,他在無聊時經常在紙上把Ranklist上每個人的ac題目的數量摘錄下來，然後從中選擇一部分人(或者全部)按照ac的數量分成兩組進行比較，他想使第一組中的最小ac數大于第二組中的最大ac數，但是這樣的情況會有很多，聰明的你知道這樣的情況有多少種嗎?

特别說明：為了問題的簡化，我們這裡假設摘錄下的人數為n人，而且每個人ac的數量不會相等，最後結果在64位整數範圍内.

Input

輸入包含多組資料，每組包含一個整數n,表示從Ranklist上摘錄的總人數。

Output

對于每個執行個體，輸出符合要求的總的方案數，每個輸出占一行。

Sample Input

2
4      

Sample Output

1
17      

Author

Eddy

題解：考組合數學

假設n個人的ac數量按從小到大排列，可以從中任選m個人(n=>m>=2)，

再把這m個人分2組(每個人都要分組)，要是滿足最小ac數大于最大ac數，隻需要在m

個人中插闆即可。例如： 

m個人假如分别為 ： 

1，2，3，4，......m-1，m (m個人的ac數從小到大排列) 

隻需在任意位置插闆就可分為符合要求的2組： 

1，2，3......t， || t+1...m-1，m (1<=t<m) 

則 1，2，3......t 為一組 

t+1，t+2，......m-1，m 為一組 

很明顯這樣分組符合要求，在這m人中共有m-1種分法(t取不同值) 

AC代碼：

#include<iostream>     
#include<cstdlib>    
#include<cstdio>    
#include<cmath>    
#include<cstring>    
#include<string>    
#include<cstdlib>    
#include<iomanip>    
#include<vector>    
#include<list>    
#include<map>    
#include<queue>  
#include<algorithm>    
using namespace std;

double c(double a)  //a!
{
  double i,s=1;
  for(i=1;i<=a;i++)
    s=s*i;   
  return s;
}
double f(double n,double i)
{
  return c(n)/( c(n-i)*c(i) ); // n!/(n-i)!*i!
}
int  main()
{
  double i,n,sum;
  while(scanf("%lf",&n)!=-1)
  {
    sum=0;
    for(i=2;i<=n;i++)
      sum=sum+(i-1)*f(n,i);
    printf("%.0f\n",sum);
  }
  return 0;
}