NYOJ 127 星際之門 - 完全圖生成樹計數 + 快速冪

問題描述

N 個星系，修建 N-1 條蟲洞連通所有星系。有多少種修建方案？結果模 10003。N≤1e6，T≤100。

數學結論：Cayley 公式

N 個標號點的完全圖，生成樹數量 = N^(N-2)（Cayley 公式）。需計算 N^(N-2) mod 10003。

快速冪模運算

二進制分解指數，O(log N) 計算。注意 N=2 時指數為 0，結果為 1。

代碼實現（C++）

#include 
using namespace std;
const int MOD = 10003;

int modPow(int a, long long e) {
    long long res = 1, base = a % MOD;
    while (e > 0) {
        if (e & 1) res = res * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return (int)res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        long long n; cin >> n;
        if (n == 2) { cout << 1 << '\n'; continue; }
        cout << modPow(n % MOD, n - 2) << '\n';
    }
    return 0;
}

優化：指數過大可用歐拉定理減指數

MOD=10003 為質數，φ(10003)=10002。若 n-2 ≥ 10002，可先對 10002 取模。但 n≤1e6，log(n) 很小，直接快速冪足夠。