UVa 11609 Teams (组合数学)

本文主要是介绍UVa 11609 Teams (组合数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVa 11609 Teams

---

题目大意:

有$n(1\leq n\leq 10^9)$个人,选一个或者多个人参加比赛,其中一名当队长.两种方案相同,当且仅当人员组成和队长相同,问有多少种方案.
输出方案数除以1000000007的余数.

题目分析:

(推个式子都要推半天,吃枣药丸)

当选择1个人的时候有$C_{n}^{1}$种方案,每种方案队长安排有1种.
当选择2个人的时候有$C_{n}^{2}$种方案,每种方案队长安排有2种.
…

$ans\\=1*C_{n}^{1}+2*C_{n}^{2}+...+n*C_{n}^{n}$
$=\sum_{i=1}^{n} i*C_{n}^{i}$

对于任意i,有

$i*C_{n}^{i}\\=i*\frac{n!}{i!(n-i)!}$
$=\frac {n(n-1)!}{(i-1)![(n-1)-(i-1)]!}$
$=n*C_{n-1}^{i-1}$

所以

$ans\\=n*\sum_{i=1}^{n}C_{n-1}^{i-1}$
$=n*2^{n-1}$

代码:

#include<cstdio>
#include<iostream>
#include<algorithm>using namespace std;const int MOD=1000000007;int pow_mod(int x,int y)
{int ret=1;while(y>0) {if(y&1) ret=1ll*ret*x%MOD;x=1ll*x*x%MOD;y>>=1;}return ret;
}int main()
{int T,kase=0,n;scanf("%d",&T);while(T--) {scanf("%d",&n);printf("Case #%d: %lld\n",++kase,1ll*n*pow_mod(2,n-1)%MOD);}return 0;
}

这篇关于UVa 11609 Teams (组合数学)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---