# 随机分析：直接期望递推

配套讲解的期望递推解法；Codex（GPT-6）整理为滚动存储，明确同时更新的取值顺序。程序：[alternative-direct-expectation.cpp](alternative-direct-expectation.cpp)。首选方案见[主解](solution.zh.md)。

## 方法与证明

模数记为 $M=998244353$ .

初始化各位置期望 $x_j=a_j$ ，计算不变的平均值 $\mu=n^{-1}\sum a_j$ .第 $i$ 轮先保存旧值 $c=x_i$ ，对每个 $j\ne i$ 更新

$$x_j\gets(n-1)n^{-1}x_j+n^{-1}c\pmod M$$

最后令 $x_i=\mu$ .独立均匀抽样使位置 $j$ 有 $1/n$ 的概率收到位置 $i$ 的旧值，其余情况不变；位置 $i$ 则收到均匀选择的位置的值。因此公式准确描述一轮期望。对轮次归纳，最终数组就是所求结果。

必须先保存 $c$ ，不能把已经更新的 $x_i$ 用于同一轮的其他位置。不需要保留历史轮次，因为这一轮只依赖每个位置自己的旧值和共同的 $c$ .

## 复杂度与适用范围

总时间 $O(n^2+\log M)$ ，空间 $O(n)$ .$n=1$ 也可以直接按公式运行，无须求 $(n-1)^{-1}$ .该实现最直接地对应单轮公式；仿射主解通过合并共同更新减少为线性轮次处理。

这是完整范围的正确备用方案。具体参考时限下的结果见[主解实测](solution.zh.md#实测结果)，更高时间阶不意味着当前规模必定超时。