UVA 11181 Probability|Given：條件概率 DP（貝葉斯公式 + 遞歸）

問題建模

N 個人獨立購物，第 i 人購買概率 p_i。已知**恰好** r 人購買，求第 i 人購買的條件概率 P(i買 | 總共r人買)。

貝葉斯公式

P(i買 | r人買) = P(i買 ∧ 總共r人買) / P(總共r人買)。
分子 = p_i × P(其餘N−1人中恰r−1人買)。
分母 = P(N人中恰r人買)。

遞歸計算概率

定義 `dfs(pos, left, prob)` = 從第 `pos` 個人開始，剩餘需買 `left` 人，當前概率乘積 `prob` 的總和。
遞歸：
`dfs(pos, left, prob) = dfs(pos+1, left-1, prob * p[pos]) + dfs(pos+1, left, prob * (1-p[pos]))`。
出口：`pos > N` 返回 `left==0 ? prob : 0`。
同時在遞歸中累加分子 `ans[i]`（當選中第 i 人買時的概率和）。

代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;

double p[MAXN], ans[MAXN];
int N, R;

double dfs(int pos, int left, double prob) {
    if (pos > N) return left == 0 ? prob : 0;
    double sum = 0;
    if (left > 0) {
        sum += dfs(pos + 1, left - 1, prob * p[pos]);
        ans[pos] += sum; // 此處需修正：應在調用前記錄
    }
    sum += dfs(pos + 1, left, prob * (1 - p[pos]));
    return sum;
}

// 修正版：分子單獨計算
double calc(int pos, int left, double prob, int target) {
    if (pos > N) return left == 0 ? prob : 0;
    double res = 0;
    if (pos == target) {
        if (left > 0) res += calc(pos + 1, left - 1, prob * p[pos], target);
    } else {
        if (left > 0) res += calc(pos + 1, left - 1, prob * p[pos], target);
        res += calc(pos + 1, left, prob * (1 - p[pos]), target);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int caseNo = 0;
    while (cin >> N >> R, N || R) {
        for (int i = 1; i <= N; ++i) cin >> p[i];
        fill(ans, ans + MAXN, 0);
        double denom = 0;
        // 計算分母：N 人中恰 R 人買
        function dfsAll = [&](int pos, int left, double prob) {
            if (pos > N) return left == 0 ? prob : 0.0;
            double s = 0;
            if (left) s += dfsAll(pos+1, left-1, prob * p[pos]);
            s += dfsAll(pos+1, left, prob * (1-p[pos]));
            return s;
        };
        denom = dfsAll(1, R, 1.0);
        // 計算每個人的分子
        for (int i = 1; i <= N; ++i) {
            function dfsOne = [&](int pos, int left, double prob) {
                if (pos > N) return left == 0 ? prob : 0.0;
                if (pos == i) {
                    if (left == 0) return 0.0;
                    return dfsOne(pos+1, left-1, prob * p[pos]);
                } else {
                    double s = 0;
                    if (left) s += dfsOne(pos+1, left-1, prob * p[pos]);
                    s += dfsOne(pos+1, left, prob * (1-p[pos]));
                    return s;
                }
            };
            ans[i] = dfsOne(1, R, 1.0);
        }
        cout << "Case " << ++caseNo << ":\n";
        for (int i = 1; i <= N; ++i)
            cout << fixed << setprecision(6) << ans[i] / denom << '\n';
    }
    return 0;
}

優化

N ≤ 20，狀態數 ≤ 20×20 = 400，可用記憶化 DP（`dp[pos][left]`）將指數遞歸降為 O(N×r)。