Teams (UVA 11609)：組合計數與快速冪

問題描述

有 n 人，選若干人組隊，且指定一名隊長（隊長不同視為不同方案）。求方案數模 1e9+7。

組合推導

選隊長 n 種，其餘 n-1 人每人選或不選（2 種狀態），共 n * 2^{n-1} 種方案。需模 MOD = 1,000,000,007 計算。

快速冪模板

long long mod_pow(long long a, long long e) {
    long long r=1;
    while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; }
    return r;
}

完整代碼

#include 
#define MOD 1000000007
#define LL long long

LL mod_pow(LL a, LL e) {
    LL r=1;
    while(e){ if(e&1) r=r*a%MOD; a=a*a%MOD; e>>=1; }
    return r;
}

int main() {
    int T, cas=1; scanf("%d",&T);
    while(T--) {
        LL n; scanf("%lld",&n);
        LL ans = n * mod_pow(2, n-1) % MOD;
        printf("Case #%d: %lld\n", cas++, ans);
    }
    return 0;
}

關鍵點

• n 可達 10^9 以上，必須用快速冪。
• n=0 時題意未定義，但輸入保證 n≥1。
• 輸出格式 Case #x: ans。

總結

UVA 11609 是組合計數 + 快速冪的極簡題。核心公式 n * 2^{n-1} 來源於「先選隊長，再任意選隊員」。掌握快速冪模板，此類模冪取模問題秒解。