首页 > 代码库 > UVa 11609 - Teams

UVa 11609 - Teams

题目:n个人中取出k个人组成一个小组,并且其中有一名组长,问有多少种取法。

分析:分治、组合数学。F(n) = C(n,1)*1 + C(n,2)*2 + ... = sum(C(n,i)*i)

            推导:C(n,i)*i=n*...*(i+1)/ [i*(i-1)*...*1] * i=n * [(n-1)*...*i]/ [i*...*1]=C(n-1,i)*n

                         F(n)= n*sum(C(n-1,i))= n * 2^(n-1)

            利用快速幂求解即可。

说明:使用long long防止溢出;用%I64d竟然PE(⊙_⊙)。

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

long long N,MOD = 1000000007;

long long spow( long long x, long long n )
{
	if ( n == 0LL ) return 1LL;
	if ( n == 1LL ) return x%MOD;
	long long v = spow( x, n/2LL );
	if ( n%2LL == 1LL ) 
		return ((v*v)%MOD*x)%MOD;
	else return (v*v)%MOD;
}

int main()
{
	int T;
	while ( cin >> T )
	for ( int t = 1 ; t <= T ; ++ t ) {
		cin >> N;
		printf("Case #%d: %lld\n",t,spow(2LL,N-1LL)*N%MOD);
	}
	return 0;
}