看题传送门

题目大意：

有n个人，选一个或者多个人参加比赛，其中一名当队长，如果参赛者相同，队长不同，也算一种方案。求一共有多少种方案。

思路：

排列组合问题。

先选队长有C(n , 1)种

然后从n-1个人中选，但人数不确定，所以应是1个~n-1个人的和。

比如n=1，那么就是C(n , 1)种

n=2 那么就是 C(n , 1)  +  C(n ,1) * C(n-1 , 1)

n=3那么就是 C(n , 1)  +  C(n ,1) * C(n-1 , 1)  +  C(n , 1) * C(n-1 , 2)   （一个人+两个人+三个人）

也就是说一共有（哈哈word的公式编辑器）  ：）

还有就是用快速幂取模~

用位运算来做的。不过速度竟然比递归的慢，这是为啥？

#include<cstdio>

const int mod=1000000007;

typedef long long LL;

LL mypow(LL a,LL n)

{

	LL res = 1,temp = a;

	while(n)

	{

		if( n & 1)  res=res * temp % mod;

		temp=temp * temp % mod;

		n>>=1;

	}

	return res;

}

int main()

{

	int T,n,kase=1;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		printf("Case #%d: %lld\n",kase++,mypow(2,n-1) * n % mod);

	}

	return 0;

}

递归版本

#include <cstdio>

const int mod= 1000000007;

typedef long long LL;

LL pow_mod(const LL &a,const LL &p) //a^p % n

{

	if(p==0) return 1;

	LL ans=pow_mod(a,p/2);

	ans=ans *ans % mod;

	if(p%2==1) ans=ans*a % mod;

	return ans;

}

int main()

{

	int T;

	scanf("%d",&T);

	for(int ri=1;ri<=T;ri++)

	{

		int n;

		scanf("%d",&n);

		LL ans=pow_mod (2,n-1) * n % mod;

		printf("Case #%d: %lld\n",ri,ans);

	}

	return 0;

}