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

有n个人,选一个或多个人参赛,其中一人为队长,求有多少种选法,结果对100000007取模。

根据题意结果为1C(n,1)+2C(n,2)+……+n*C(n,n)对100000007取模的值。

有组合数公式:1C(n,1)+2C(n,2)+……+nC(n,n)=n2^(n-1)

然后用快速幂取模就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
const long long maxn=1000000007;
long long modexp(int a,int b){
long long ret=1;
long long tmp=a;
while(b){
if(b&1) ret=ret*tmp%maxn;
tmp=tmp*tmp%maxn;
b>>=1;
}
return ret;
}
int main(){
int n,t=0;
cin>>n;
while(n--){
int a;
cin>>a;
cout<<"Case #"<<++t<<": ";
cout<<(modexp(2,a-1)*a)%maxn<<endl;
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **