这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
传送门: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;
}