LightOJ 1038 Race to 1 Again：期望 DP + 方程變形求解

問題描述

從 N 開始，每步隨機選一個因子 d ∈ [1, N]（若 d 不整除 N 則不合法？題目實為：選 N 的任意因數），將 N ← N/d。求期望步數使 N 變為 1。N ≤ 1e5，T ≤ 10000。

期望方程建立

設 E[n] 為從 n 到 1 的期望步數。E[1] = 0。
對於 n > 1，其因數集合為 D(n)，大小 cnt。每步等概率選一個因數 d：

E[n] = 1 + (1/cnt) × Σ_{d∈D(n)} E[n/d]

注意 d=n 時 n/d=1，E[1]=0。將含 E[n] 的項（對應 d=1）移到左邊：

E[n] - (1/cnt)·E[n] = 1 + (1/cnt) × Σ_{d∈D(n), d>1} E[n/d]

E[n] × (cnt-1)/cnt = 1 + (1/cnt) × Σ' E[n/d]

E[n] = (cnt + Σ' E[n/d]) / (cnt - 1)

其中 Σ' 為除 d=1 外所有因數的期望和，cnt = |D(n)|。

預計算所有 E[n]

因 n/d < n（對 d>1），可按 n=2..1e5 遞推計算：

const int MAXN = 100005;
double E[MAXN];

void precompute() {
    E[1] = 0;
    for (int n = 2; n < MAXN; n++) {
        double sum = 0;
        int cnt = 0;
        for (int d = 1; d * d <= n; d++) if (n % d == 0) {
            // 因子 d
            sum += E[n/d];
            cnt++;
            if (d != n/d && d != 1) { // 因子 n/d，避免重複計算 d=1 對應的 n
                sum += E[d];
                cnt++;
            }
        }
        // 公式：E[n] = (cnt + sum) / (cnt - 1)
        // 注意：sum 已包含 E[1]=0 (對應 d=n)，cnt 含 d=1
        E[n] = (cnt + sum) / (cnt - 1);
    }
}

關鍵細節修正

上述代碼中因子枚舉需精確對應公式。更清晰的寫法：

int cnt = 0; double sum = 0;
for (int d = 1; d * d <= n; d++) if (n % d == 0) {
    // 因子 d
    sum += E[n/d]; // 對應因子 d，下一狀態 n/d
    cnt++;
    if (d != n/d) {
        sum += E[d]; // 對應因子 n/d，下一狀態 d
        cnt++;
    }
}
// 此時 cnt = 因子總數，sum = Σ E[n/d] (含 d=1 項 E[n])
// 公式：E[n] = 1 + sum/cnt  =>  E[n]*(1 - 1/cnt) = 1 + (sum - E[n])/cnt
// 即 E[n] = (cnt + sum - E[n]) / (cnt - 1) ? 
// 正確推導：
// E[n] = 1 + (1/cnt)*(E[n] + Σ_{d>1} E[n/d])
// E[n] - E[n]/cnt = 1 + (sum - E[n])/cnt
// E[n]*(cnt-1)/cnt = 1 + sum/cnt - E[n]/cnt
// E[n]*(cnt-1) = cnt + sum - E[n]
// E[n]*cnt = cnt + sum
// E[n] = (cnt + sum) / cnt
// 但 sum 包含 E[n] (對應 d=1)，所以 sum = E[n] + Σ_{d>1} E[n/d]
// 代入：E[n] = (cnt + E[n] + Σ') / cnt  =>  E[n]*cnt = cnt + E[n] + Σ'  =>  E[n]*(cnt-1) = cnt + Σ'
// 所以 E[n] = (cnt + Σ') / (cnt - 1)
// 其中 Σ' = sum - E[n]
// 避免循環依賴，直接用：
// E[n] = (cnt + sum - E[n]) / (cnt - 1)  // 仍含 E[n]
// 最簡單：預先把 sum 算為 Σ_{d>1} E[n/d]

最終正確版預計算

E[1] = 0; E[2] = 2; // 基礎情況
for (int n = 3; n < MAXN; n++) {
    double sum = 0;
    int cnt = 0;
    for (int d = 1; d * d <= n; d++) if (n % d == 0) {
        if (d > 1) { sum += E[n/d]; cnt++; }
        int d2 = n/d;
        if (d2 != d && d2 > 1) { sum += E[d2]; cnt++; }
    }
    // 現在 cnt = 因子數 - 1 (排除 1)，sum = Σ_{d>1} E[n/d]
    E[n] = (cnt + 1 + sum) / cnt; // 公式：(cnt_total + Σ') / (cnt_total - 1)
    // 其中 cnt_total = cnt + 1
}

複雜度與優化

• 預計算：O(N √N) ≈ 1e5 × 316 ≈ 3e7，可接受
• 查詢：O(1)
• 可用線性篩法預計算所有因數列表，優化至 O(N log N)

樣例驗證

此題核心在於「期望方程含未知項」的代數變形，將遞歸依賴消除，實現自底向上 DP。預計算 + O(1) 查詢完美應對多測試用例。