UVa 11609 - Teams（组合数＋快速幂）

发表于 分类于 ， ， Disqus：

有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博客，格式可能有所偏差。 **

相关文章