LightOJ 期望迷宮：數學期望公式推導

問題描述

迷宮有 n 扇門。門 i 值 x_i：>0 表示 x_i 分鐘後出去；<0 表示 |x_i| 分鐘後回到起點。每次隨機選門。求走出迷宮的期望時間。

期望方程建立

設期望為 E。k 扇正門（值 a_j），m 扇負門（值 b_j），n=k+m。
E = (1/n) * Σ a_j + (1/n) * Σ (b_j + E)
解得：E = (Σ a_j + Σ b_j) / (n - m) = Σ |x_i| / (正門數)。
若無正門（m=n），期望無限大，輸出 inf。

代碼實現

int gcd(int a,int b){ return a?gcd(b%a,a):b; }
int main() {
    int T,cas=1; scanf("%d",&T);
    while (T--) {
        int n; scanf("%d",&n);
        int pos=0, neg=0, cntNeg=0;
        for (int i=0;i0) pos+=x;
            else { neg+=-x; cntNeg++; }
        }
        printf("Case %d: ", cas++);
        if (cntNeg==n) { puts("inf"); continue; }
        int num = pos+neg, den = n-cntNeg;
        int g = gcd(num, den);
        printf("%d/%d\n", num/g, den/g);
    }
    return 0;
}

關鍵點

• 期望方程利用「回到起點後過程重啟」的無記憶性。
• 分數化簡輸出，分母為正門數。
• 全負門輸出 inf。

總結

LightOJ 此題是期望 DP 的簡化版：建立方程直接求解。關鍵在於識別「負門導致遞歸期望」並解線性方程。分數化簡用 gcd，注意 inf 特判。