LightOJ 1317 Throwing Balls into Baskets 概率 DP：期望值線性性質巧妙應用

LightOJ 1317：向籃子投球的期望球數

n 人、m 個籃子、k 輪。每輪每人隨機選一個籃子投球，命中概率 p。求 k 輪後所有籃子球數總期望。利用期望線性性質：總期望 = k × (單輪期望)。單輪中 i 個人命中的概率為二項分布，期望球數 = Σ i × C(n,i) pⁱ (1-p)ⁿ⁻ⁱ = n×p。但題目要求精確計算分布後乘 k。

動態規劃計算單輪分布

double dp[20], a[20], b[20]; // dp[i]: i人命中概率
double cm(int n, int m) { // 組合數 C(n,m)
    double ans = 1;
    for (int i=1; i<=m; i++) ans = ans * n-- / i;
    return ans;
}
int main() {
    int T, cas=1; scanf("%d",&T);
    while (T--) {
        int n,m,k; double p; scanf("%d%d%d%lf",&n,&m,&k,&p);
        a[0]=b[0]=1;
        for (int i=1;i<=n;i++) a[i]=a[i-1]*p, b[i]=b[i-1]*(1-p);
        for (int i=0;i<=n;i++) dp[i]=cm(n,i)*a[i]*b[n-i];
        double w=0;
        for (int i=1;i<=n;i++) w += dp[i]*i; // 單輪期望
        printf("Case %d: %.10lf\n", cas++, w*k);
    }
    return 0;
}

數學簡化

實際上單輪每個籃子期望球數 = n×p/m，總期望 = m × k × n×p/m = k × n × p。但題目可能要求展示 DP 過程，代碼按分布計算更通用。

複雜度

O(n) 預計算組合與概率，O(n) 求期望，極快。n ≤ 500 時組合數用 double 足夠精度。