POJ 1189 釘子與小球：拔除釘子後的落槽概率 (DP)

問題描述

三角形木板上釘有 n(n+1)/2 顆釘子（2 ≤ n ≤ 50），底部有 n+1 個槽（編號 0..n）。小球從頂端釘子落下，每碰一釘等概率向左/右彈開（各 1/2）。現拔除部分钉子（最底層不拔），求小球落入第 m 個槽的概率，以既約分數形式輸出（0 輸出 0/1）。

解題思路：動態規劃 + 分數運算

1. 狀態定義：dp[i][j] 表示到達第 i 行第 j 顆釘子的「球數」。為避免浮點誤差，假設頂端有 2^n 顆球，所有運算均為整數。
2. 初始化：dp[1][1] = 2^n。
3. 轉移：若釘子 (i,j) 存在（未拔除），則將其球數平均分配給下一行的左/右釘子：

   dp[i+1][j]   += dp[i][j] / 2;  // 左下
   dp[i+1][j+1] += dp[i][j] / 2;  // 右下
   

   若釘子不存在，球直接穿過，繼續向下落至下一行同位置（視為繼承該釘子的球數）。
4. 底層處理：第 n+1 行對應槽，dp[n+1][m+1] 即為落入第 m 槽的球數。
5. 約分：分子 num = dp[n+1][m+1]，分母 den = 2^n，求最大公約數 g = gcd(num, den)，輸出 num/g/den/g。

關鍵代碼片段 (C++)

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

LL dp[55][55];
bool nail[55][55];  // true = 存在

LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }

int main() {
    int n, m;
    while (cin >> n >> m) {
        memset(nail, 0, sizeof(nail));
        memset(dp, 0, sizeof(dp));
        // 讀入釘子狀態，忽略空格
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                char ch;
                do { cin >> ch; } while (ch != '*' && ch != '.');
                nail[i][j] = (ch == '*');
            }
        }
        dp[1][1] = 1LL << n;  // 2^n
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (!nail[i][j]) continue;  // 拔除的釘子不分發
                LL half = dp[i][j] / 2;
                dp[i+1][j]   += half;
                dp[i+1][j+1] += half;
            }
        }
        LL num = dp[n+1][m+1];
        LL den = 1LL << n;
        LL g = gcd(num, den);
        cout << num/g << '/' << den/g << '\n';
    }
    return 0;
}

複雜度分析

• 釘子總數 O(n^2) ≤ 1275，DP 狀態同階。
• 時間 O(n^2)，空間 O(n^2)，極快。
• 使用 long long（64 位）足夠：2^50 ≈ 1.1×10^15 < 9×10^18。

總結

POJ 1189 將概率問題轉化為整數流分配問題，巧妙避開了浮點精度陷阱。關鍵在於：以 2^n 為分母統一尺度，拔除釘子視為「不分發、直接穿透」，底層槽直接累積球數。最後用輾轉相除法約分，得到既約分數。代碼簡潔，思路清晰，是 DP 處理概率問題的經典範例。