BZOJ 3191 [JLOI2013] 卡牌遊戲：概率動態規劃求生存者勝率

問題描述

N 個玩家圍成一圈，編號 1 到 N 順時針。初始莊家為玩家 1。每回合莊家從 M 張卡片中等概率隨機抽取一張（數字 X），順時針數第 X 個人被淘汰，其順時針下一位成為新莊家。卡片放回重洗。進行 N-1 輪後剩一人獲勝。已知 N, M 及所有卡片數字，求每位玩家獲勝概率（百分比，保留兩位小數）。

狀態定義與轉移

令 f[i][j] 表示當前剩 i 人時，從莊家起順時針第 j 個人（1 ≤ j ≤ i）最終獲勝的概率。初始 f[1][1] = 1。

考慮從 i-1 人轉移到 i 人。新增一名玩家後，總人數變為 i。枚舉抽到的卡片 k（1 ≤ k ≤ M），其數字為 a[k]。淘汰位置 pos = (a[k] - 1) % i + 1（1-based）。

• 若 pos == j：第 j 人被淘汰，概率歸零，不轉移。
• 若 pos < j：淘汰者在 j 之前，圈縮小後，原第 j 人變為新圈中第 j-1 人，且新莊家為原 pos+1 人。相對位置需調整。
• 若 pos > j：淘汰者在 j 之後，原第 j 人位置不變，新莊家為原 pos+1 人（模 i）。

具體轉移公式需仔細處理索引映射。代碼片段中核心邏輯為：

F(i,2,n) F(j,1,i) F(k,1,m) {
    int pos = (a[k]-1)%i + 1;
    if (pos == j) continue;
    if (pos < j) f[i][j] += f[i-1][j-1] / m;
    else f[i][j] += f[i-1][j] / m;
}

（註：實際需考慮莊家位置變化，上述為簡化示意，完整邊界條件見原代碼。）

複雜度分析

狀態數 O(N²)，轉移枚舉 M 張卡片，總複雜度 O(N²M)。數據範圍 N, M ≤ 50，極限 125,000 次操作，極易通過。

實現細節

• 雙重循環遞推 i 從 2 到 N，內層 j 從 1 到 i。
• 概率均分：每張卡片概率 1/M。
• 最終答案為 f[N][1..N]，對應初始狀態下各玩家獲勝概率。
• 輸出格式：百分比，四捨五入保留兩位小數，以 % 結尾，空格分隔，末尾無空格。

總結

本題是典型的區間概率 DP，通過逆向思維（從少人數推導到多人）並結合模運算處理循環結構，巧妙解決了隨機淘汰過程中的概率分佈問題。