题意:有n个人,选多个人参加比赛,其中一个是队长,队长不同其他选手相同也算作不同的方案,问你一共有多少种方案。
思路:可以想到 答案为 1*C(1,n)+2*C(2,n)+3*C(3,n)+....+n*C(n,n);
由公式 k*C(k,n) = n*C(k-1,n-1)
所以最终答案 n*2^(n-1)
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 const int mod=1e9+7; 5 typedef long long ll; 6 ll qpow(int n) 7 { 8 ll ans=1,a=2; 9 while(n) 10 { 11 if(n%2) ans=(ans*a)%mod; 12 n/=2; 13 a=a*a%mod; 14 } 15 return ans; 16 } 17 int main(int argc, char *argv[]) 18 { 19 int t,n,cnt=0; 20 cin>>t; 21 while(t--) 22 { 23 cin>>n; 24 ll ans=1LL*n*qpow(n-1)%mod; 25 cout<<"Case #"<<++cnt<<": "<<ans<<endl; 26 } 27 return 0; 28 }View Code