HDU 5159: Card - 組合數學期望計算

問題描述

從 1~x 中選 b 個數（有序或無序？題目隱含有序選擇），求期望值。實際為：所有 C(x,b) 種組合等概率，每個數被選中的期望次數相同，期望和 = (每個數期望被選次數) × (1+...+x) / 總組合數。

推導

每個數在所有組合中出現次數 = C(x-1, b-1)。
所有組合元素和總和 = C(x-1, b-1) * x(x+1)/2。
期望值 = 總和 / C(x,b) = b(x+1)/2。
但題目樣例輸出為浮點數，實際計算 dp[x][b] / x^b（有序選擇）。預計算 dp[i][j] 為所有長度 j 序列元素和總和，遞推：dp[i][j] = i * (i^j - (i-1)^j) * i(i+1)/2。

代碼

double dp[100001][6];
int main() {
    for (int i=1; i<=5; ++i) dp[1][i]=1;
    for (int i=2; i<=100000; ++i) {
        dp[i][1] = dp[i-1][1] + i;
        for (int j=2; j<=5; ++j) {
            double a1=1, a2=1;
            for (int k=1; k