39 · 概率与期望入门

先处理输入。这不是“读 n 个数”，而是读 5 个参数再按规则生成 a。规则里有个陷阱：qᵢ 用的是还没 mod C 的 qᵢ₋₁ 迭代，两步必须分开——先把整串 q 生成完，再统一做 aᵢ = qᵢ mod C + 1。混在一起写，从第 2 项起就全错。

概率部分：设 Xᵢ = 1 表示“抄到第 i+1 题位置上的那个答案，恰好等于第 i+1 题的正确答案”。第 n 题的答案填在第 1 题的位置，所以 Xₙ 看的是第 1 题。做对的题数 X = X₁ + X₂ + … + Xₙ，每个 Xᵢ 只取 0 或 1。

由线性性，E[X] = Σ E[Xᵢ] = Σ P(Xᵢ = 1)。这一步把题目之间的所有关联切断了：不需要知道 2ⁿ 种全局情况，也不需要管 X₁ 与 X₂ 是不是独立，每题单独算概率就行。

算 P(Xᵢ = 1)。第 i+1 个位置上写的是“第 i 题的正确答案”，它在 1..aᵢ 上均匀，概率 1/aᵢ；第 i+1 题的正确答案在 1..a_{i+1} 上均匀，概率 1/a_{i+1}，而且两者独立。于是

P = Σ_{v=1}^{min(aᵢ,aᵢ₊₁)} (1/aᵢ)(1/aᵢ₊₁) = min/(aᵢ·aᵢ₊₁) = 1/max(aᵢ, aᵢ₊₁)。一个“最小值除以乘积”，化简后就是一个“最大值取倒数”。

所以答案 = Σ_{i=1}^{n} 1/max(aᵢ, aᵢ₊₁)，其中 a_{n+1} = a₁。用样例 a = {2,3,1} 验算：1/3 + 1/3 + 1/2 = 7/6 ≈ 1.167，与题面一致。

实现：n ≤ 10⁷，开数组要 40 MB；但每一项只依赖相邻两个 a，边生成边累加即可，额外空间 O(1)。注意第 n 题的答案要填到第 1 题，所以循环结束后还差一项，别漏。

精度：n 项相加，每项 ≤ 1，和 ≤ 10⁷。double 的相对误差 10⁻¹⁶，累加 n 项的绝对误差约 10⁻⁹ 量级，保留三位小数完全安全。

模板只有五行（示意，真实的边枚举那一行要换成你自己的循环）。看清楚那个“1”是什么：它是走一步本身的代价，不是概率。

dp[终点] = 0;                                  // 边界：到终点不用再走
for (状态 s，按"离终点从近到远"的顺序) {        // 倒序！通常就是逆拓扑序
    dp[s] = 0;
    for (每个一步可达的 t)                          // 换成你的边枚举
        dp[s] += p(s -> t) * (cost(s -> t) + dp[t]);   // 全期望公式
}
// 答案 = dp[起点]

例：一枚均匀骰子，每次掷出 1~6 中的一个。从位置 0 出发，走到 ≥ n 就停，求步数期望。

设 dp[i] = 从位置 i 出发到结束的期望步数。i ≥ n 时已经结束，dp[i] = 0。i < n 时掷出 k（概率 1/6），花费 1 步，到达 min(i+k, n)。于是

dp[i] = 1 + (1/6) · Σ_{k=1..6} dp[ min(i + k, n) ]

这个方程“自己包含自己”，但 dp[i] 只依赖 i+1..i+6，全是更大的下标，所以从 n−1 倒着扫一遍就能一次算完，不需要解方程。

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

int main() {
    int n;
    cin >> n;

    vector<double> dp(n + 7, 0.0);        // dp[n..n+6] = 0：已经到达或越过终点
    for (int i = n - 1; i >= 0; --i) {    // 倒着扫：dp[i] 只依赖更大的下标
        double s = 0;
        for (int k = 1; k <= 6; ++k) s += dp[min(i + k, n)];
        dp[i] = 1 + s / 6;                // 那个 1 是"这一步"本身的代价
    }

    printf("%.6f\n", dp[0]);
    return 0;
}