uva 11609 - Teams(组合数学+快速幂)

题目链接：uva 11609 - Teams

题目大意：给出n，表示说有n个人，标好1~n，现在选若干人组成一队，并且选出一个队长，问说可以选多少种队伍，队长，人数，成员不同均算不同的队伍。

解题思路：枚举人数为1、2....n的情况，那么就有1*C(n,1)+2*C(n,2)+3*C(n,3)+4*C(n,4) .....n*C(n,n),然后从中提取出n，每一项前的系数刚好与C约分。n*(C(n-1,0) + C(n-1,1) ....+C(n-1,n-2)+C(n,n)),注：C(n,n) = C(n-1,n-1)

然后后面的即为(1+1)^n的展开项。剩下的就是快速幂，注意要用long long。

#include <stdio.h>
#include <string.h>

typedef long long ll;
const ll MOD = 1000000007;

ll sPow (ll a, ll n) {
	ll x = 1;

	while (n) {
		if (n&1)
			x = (x * a) % MOD;

		n /= 2;
		a = (a * a) % MOD;
	}
	return x;
}

int main () {
	int cas;
	ll n;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		scanf("%lld", &n);
		printf("Case #%d: %lld\n", i, n * sPow(2, n-1) % MOD);
	}
	return 0;
}