BZOJ 2134 單選錯位：期望 DP 簡單應用

題目大意

有 n 道單選題，正確答案為 a[1..n]。但考生將第 i 題的答案填在了第 i%n + 1 題位置 (循環右移一位)。每題選項數為 a[i]，隨機猜中機率為 1/a[i]。求期望得分。

核心觀察

第 i 題的答案被填到第 j = i%n+1 位置。此時第 j 位置的正確答案選項數為 a[j]，而填入的答案來自第 i 題，其選項數為 a[i]。要得分，填入的選項必須恰好等於正確答案。由於答案均勻隨機，概率為 1 / max(a[i], a[j])。(因為只有當兩題選項數相同時才可能匹配，且匹配機率為 1/a[i] = 1/a[j]；若選項數不同，填入的選項範圍可能超出正確答案範圍，但題目隱含條件使得概率公式化為此。)

期望線性性

總期望 = Σ 各題期望。第 i 題貢獻期望 = 1.0 / max(a[i], a[i%n+1])。

代碼實作

#include 
#include 
using namespace std;
const int M = 10001000;
int a[M];
int main() {
    int n, A, B, C;
    scanf("%d%d%d%d%d", &n, &A, &B, &C, a+1);
    for (int i = 2; i <= n; ++i)
        a[i] = ((long long)a[i-1] * A + B) % 100000001;
    for (int i = 1; i <= n; ++i)
        a[i] = a[i] % C + 1; // 選項數在 [1, C]
    double ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += 1.0 / max(a[i], a[i % n + 1]);
    printf("%.3lf\n", ans);
    return 0;
}

複雜度

• 生成數列：O(n)
• 計算期望：O(n)
• 記憶體：O(n) (可優化為 O(1) 滾動，但 n ≤ 1e7 尚可接受)

關鍵點

1. 識別出期望可分解為獨立項求和。
2. 推導出單題期望公式 1/max(a[i], a[i%n+1])。
3. 注意 long long 防溢位生成數列。
4. 輸出格式 %.3lf 保留三位小數。