UVA11609 Teams 题解

· · 题解

大致题意

一共有 n 个人，从中选出至少一人参加比赛，有一位队长，共有多少种选择方案，最后答案对于 10^{9}+7 取模。

做法分析

根据排列组合，我们可以得出在选择队长时，有 n 种方案，而现在还剩下 n-1 人，因为已经有了队长一人了，所以剩下的人数范围为 0\le s\le (n-1)，而在 n 人中选 0 人的方案数为 C_{n-1}^{0}，选 1 人的方案数为 C_{n-1}^{1}，以此类推。

所以，最终我们可以得到总方案数为：

\begin{aligned} S &= (C_{n-1}^{0}+C_{n-1}^{1}+C_{n-1}^{2}+…+C_{n-1}^{n-1})\times n\\ &= \sum_{i=0}^{n-1}C_{n-1}^{i}\times n \\ &=2^{n-1}\times n \end{aligned}

最后答案对于 10^{9}+7 取模即可。

各部分代码

由于数据比较大，所以本题需要使用快速幂对于 2^{n-1} 进行计算，下面是快速幂的代码：

#define ll long long
const int p=1e9+7;
ll poww(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=a*ans%p;
        b>>=1;
        a=a*a%p;
    }
    return ans;
}

最后每次输入一次计算即可。

AC code

#include<iostream>
#define ll long long
using namespace std;
const int p=1e9+7;
ll poww(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=a*ans%p;
        b>>=1;
        a=a*a%p;
    }
    return ans;
} 
int main(){
    ll t;
    cin>>t;
    ll n;
    for(int i=1;i<=t;i++){
        cin>>n;
        cout<<"Case #"<<i<<": "<<n*poww(2,n-1)%p<<endl;
    }
    return 0;
}