HDU 4704 Sum：隔板法 + 費馬小定理求 2^{n-1} 模 1e9+7

題目大意

將整數 n 拆分為若干正整數之和（順序相關），設 S_i 為拆成 i 份的方案數。求 Σ S_i (1≤i≤n) mod 1,000,000,007。n 可達 10⁵ 位（超大整數）。

組合數學：隔板法

n 個 1 排成一行，中間 n-1 個縫隙。插入 i-1 個隔板分成 i 份 → C(n-1, i-1) 種。
總方案數 = Σ C(n-1, k) (k=0..n-1) = 2^{n-1}。

大指數取模：費馬小定理

模數 p = 1,000,000,007 為質數，2 與 p 互質。
費馬小定理：2^{p-1} ≡ 1 (mod p)。
故 2^{n-1} mod p = 2^{(n-1) mod (p-1)} mod p。
只需將超大整數 n 以字符串讀入，計算 (n-1) mod (p-1)，再快速冪。

C++ 代碼

#include 
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
const LL PHI = MOD - 1; // 費馬小定理指數模數

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

LL strMod(const string& s, LL mod) {
    LL res = 0;
    for (char c : s) res = (res * 10 + c - '0') % mod;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string n;
    while (cin >> n) {
        LL exp = (strMod(n, PHI) - 1 + PHI) % PHI; // (n-1) mod (p-1)
        cout << modPow(2, exp, MOD) << '\n';
    }
    return 0;
}

關鍵點

• 隔板法推導 2^{n-1} 是核心數學洞察。
• 超大整數讀為字符串，逐位取模 p-1。
• (n-1) mod (p-1) 需處理負數：+ PHI 再 % PHI。
• 快速冪模板必須熟練。

總結

HDU 4704 是「組合數學 + 數論 + 大整數處理」的綜合題。核心模板：隔板法求和 → 費馬小定理降指數 → 字符串取模 → 快速冪。同類技巧適用於 HDU 4705、Codeforces 大指數取模問題。