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)

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
using namespace std;
int main()
{
    __int64 n;
    while(cin >> n)
    {
        __int64 m = 1<<(n-1);
        cout << 1+(n-2)*m << endl;
    }
    return 0;             
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注