HDOJ 2200 Eddy's AC难题

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2200

很简单的组合数学题目，不过自己没有想到隔板法，把问题想复杂了。看来开学得抓紧把组合数学看看咯。

在给定的n个数中选2到n个数进行分组，要分成2组, 由隔板法可知，如果选了i个数，

那么共有i-1种可能，则最终结果为 c(n,i) * (i-1) (i 从2开始枚举到n）的累加和

f(n) = C(n,n)(n-1)+C(n,n-1)(n-2) + C(n,n-2)(n-3) + ….. + C(n,3)2 + C(n,2)*1

= (n-1) + C(n,1)(n-2) + C(n,2)(n-2) + C(n,3)*(n-2) + ……. + C(n,n/2)(n-2)

= 1+(n-2)*(C(n,0) + C(n,1) + …… + C(n,n/2))

= 1+ (n-2)* 2^(n-1)

#include
using namespace std;
int main()
{
    __int64 n;
    while(cin >> n)
    {
        __int64 m = 1<<(n-1);
        cout << 1+(n-2)*m << endl;
    }
    return 0;             
}