HDU 5159：期望值線性性質與快速冪優化

HDU 5159 要求計算從 1..x 中每個數被選中的期望總和：每輪從 x 個數中等概率選一個，共 b 輪，求最終選中數字之和的期望。本文應用期望線性性質拆解為單個數字期望之和，利用快速冪計算概率。

問題建模

• 數字集合：{1, 2, ..., x}
• 每輪：均勻隨機選一個數（可重複選）。
• 共 b 輪。
• 設指示變量 I_i = 數字 i 是否至少被選中一次（0/1）。
• 目標：E[∑ i * I_i] = ∑ i * E[I_i] = ∑ i * P(i 被選中至少一次)。

單個數字被選中概率

每輪選中 i 的概率 = 1/x。
b 輪全不選中 i 的概率 = (1 - 1/x)^b。
至少選中一次 = 1 - (1 - 1/x)^b。
期望貢獻 = i * (1 - (1 - 1/x)^b)。
總期望 = ∑_{i=1}^x i * (1 - (1 - 1/x)^b) = (1 - (1 - 1/x)^b) * x(x+1)/2。
但題目可能要求輸出每個 Case 的期望值，直接按公式計算即可。

快速冪計算 (1 - 1/x)^b

b 可達 10⁹，需 O(log b) 快速冪。

double pow_fast(double base, int exp) {
    double res = 1.0;
    while (exp) {
        if (exp & 1) res *= base;
        base *= base;
        exp >>= 1;
    }
    return res;
}

完整代碼（C++）

#include <cstdio>
#include <cmath>
using namespace std;

double fastPow(double a, int n) {
    double r = 1;
    while (n) {
        if (n & 1) r *= a;
        a *= a;
        n >>= 1;
    }
    return r;
}

int main() {
    int T, x, b;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        scanf("%d%d", &x, &b);
        double p_not = fastPow(1.0 - 1.0/x, b);
        double p_yes = 1.0 - p_not;
        double sum = p_yes * x * (x + 1) / 2.0;
        printf("Case #%d: %.3lf\n", tc, sum);
    }
    return 0;
}

組合數學替代解法（原文第二種）

直接計算所有可能結果的加權平均：

• 選 b 次，有序，共 x^b 種等概率結果。
• 對每個數字 i，計算其在所有結果中出現的總次數，乘以 i，除以 x^b。
• 涉及斯特林數/第二類斯特林數 S(b, k) 計算「b 次選擇恰好覆蓋 k 個不同數」的方案數。
• 複雜度較高，且需高精度組合數，不如期望線性性質簡潔。

關鍵數學洞察

1. 期望線性性質：E[X+Y] = E[X] + E[Y] 無需獨立性。將「總和期望」拆解為「每個數字貢獻期望之和」。
2. 指示變量技巧：將「被選中」轉化為 0/1 變量，期望 = 概率。
3. 補集概率：計算「至少一次」用「全不選」補集更簡單。

總結

本題是「期望線性性質 + 快速冪」的教科書級應用。核心步驟：

1. 定義指示變量拆解目標期望。
2. 計算單個變量期望（概率）。
3. 利用補集簡化概率計算。
4. 大指數用快速冪。

此思路廣泛適用於「多次獨立隨機試驗，求某類事件發生期望」問題。