# 随机分析：期望

## 解法与署名

首选全局仿射维护，程序：[std.cpp](std.cpp)。Codex（GPT-6）将直接期望递推改写为统一变换和单点赋值，给出线性轮次处理的实现与证明。仿射表示与模逆元均是已有技术，贡献是它们在本题递推中的应用。

保留出题人的[逐元素概率转移](solution-alternative-element-probabilities.zh.md)及[程序](alternative-element-probabilities.cpp)，也保留配套讲解中的[直接期望递推](solution-alternative-direct-expectation.zh.md)及[程序](alternative-direct-expectation.cpp)。两种基础解法均正确；首选方案减少了每轮逐位置更新的工作。

## 单轮递推

模数记为 $M=998244353$ .设当前各位置随机变量的期望为 $x_1,\ldots,x_n$ .这些变量可以是原数组数值，也可以是某个数值的出现指示变量。交换保持它们的总和，其平均值记为 $\mu$ .

第 $i$ 轮交换位置 $i$ 与独立均匀选出的一个位置。令

$$\alpha=(n-1)n^{-1}\pmod M$$

对 $j\ne i$ ，概率 $1/n$ 的事件会把位置 $i$ 的值换到 $j$ ，其余情况位置 $j$ 不变。因此

$$x'_j=\alpha x_j+n^{-1}x_i\quad(j\ne i),\qquad x'_i=\mu$$

后一式成立，是因为位置 $i$ 换入的是均匀选择的一个当前位置的值。推导只要求本轮选择独立于此前过程，不要求不同位置的随机变量相互独立，也不假设最终排列均匀。

## 全局仿射更新

维护每个位置的系数 $b_j$ 和两个全局量 $s,t$ ，使当前期望满足

$$x_j=s b_j+t\pmod M$$

初始 $s=1,t=0,b_j=x_j$ .第 $i$ 轮先用旧的 $s,t,b_i$ 得到 $c=x_i$ ，然后执行

$$s'=\alpha s,\qquad t'=\alpha t+n^{-1}c$$

这把单轮中的共同更新同时应用到全部位置。只有位置 $i$ 需要改为 $\mu$ ，因此再令

$$b_i=(\mu-t')(s')^{-1}\pmod M$$

其余 $b_j$ 保持不变。维护 $h=s^{-1}$ ，每轮只需更新 $h'=h\alpha^{-1}$ ，无需每轮重新求逆。所有赋值必须使用更新前的 $c$ .

当 $n=1$ 时直接输出确定结果。对 $2\le n\le300$ ，$n$ 和 $n-1$ 均不为模 $M$ 的零元，所以 $\alpha$ 及每轮 $s$ 都可逆。

## 正确性

初始仿射表示成立。若一轮开始前成立，则对未单独修改系数的位置，全局更新得到 $\alpha x_j+n^{-1}c$ ；对位置 $i$ ，重设系数后得到 $\mu$ .两者分别等于正确的单轮递推，因此归纳得到全部轮次的正确期望。最后代入 $s b_j+t$ 即得到结果。

## 代入数值期望

初始 $b_j=a_j$ ，不变的平均值为

$$\mu=n^{-1}\sum_{j=1}^{n}a_j\pmod M$$

只运行一次完整的仿射更新即可输出全部 $E_j$ .两次快速幂计算逆元需要 $O(\log M)$ 次模运算，处理和输出需要 $O(n)$ ，总时间 $O(n+\log M)$ ，空间 $O(n)$ .当模数固定时，随 $n$ 的增长是线性的。

## 三种方案的取舍

| 方案 | 时间 | 空间 | 用途 |
| --- | --- | --- | --- |
| 全局仿射维护 | $O(n+\log M)$ | $O(n)$ | 首选，减少逐位置更新 |
| 直接期望递推 | $O(n^2+\log M)$ | $O(n)$ | 备用，直接对应每轮公式 |
| 逐元素概率转移 | $O(n^3+\log M)$ | $O(n)$ | 备用，便于联系元素位置概率 |

表中空间对应随题程序使用的滚动存储。当前 $n\le300$ ，三种方案均通过已测正式输入，具体耗时见文末。

所有随机选择序列共 $n^n$ 个且等概率。概率与期望可以统一写为分母为 $n^n$ 的分数，$n<M$ 保证分母可逆。乘法中间值使用 64 位整数，并在每一步取模。

若还需要完整数值分布，可阅读[概率版](../shuffle-distribution/statement.zh.md)。两题满足 $E_i=\sum_{j=1}^{n}jP_{i,j}$ ，但只求期望时不必计算矩阵。

## 验证与使用

固定种子的正式输入配方见 `tests/plan.json` .自行编译程序后运行：

```text
python tests/generate.py --out-dir <output-directory> --std <compiled-program>
```

省略 `--std` 仅生成输入；`--case 01` 选择指定用例。独立验证见 [check_r15_followup.py](../../../tools/check_r15_followup.py)，五轮计时、内存与哈希见[测量记录](../../../docs/benchmark-R15-followup.json)，环境见[评测说明](../../../docs/评测环境与性能.md)。

小规模验证枚举所有随机选择序列，并实际执行交换后计数；不使用题解中的概率递推作为唯一依据。另检查每行概率和、每列出现次数、最后一行以及期望与矩阵加权的一致性。有限测试补充正确性证明，不替代证明。

## 实测结果

在 Intel Core Ultra 9 275HX、Windows 11、GCC 16.2.0、C++17 `-O2` 环境下，每份程序在相同的十份正式输入上运行五轮。表中时间为各用例中位耗时的最大值，包含进程启动与输入输出；内存为独立测得的峰值工作集，包含运行时开销。

| 程序与算法 | 最慢中位数（秒） | 峰值（MiB） | 0.5 秒参考时限 |
| --- | ---: | ---: | --- |
| [全局仿射维护](std.cpp) | 0.030652 | 5.31 | 已测输入通过 |
| [直接期望递推](alternative-direct-expectation.cpp) | 0.032607 | 5.33 | 已测输入通过 |
| [逐元素概率转移](alternative-element-probabilities.cpp) | 0.054410 | 5.32 | 已测输入通过 |

参考时限由标程最慢中位数乘以 2，再向上取整到 0.5 秒得到。完整轮次、输入与源码哈希见[测量记录](../../../docs/benchmark-R15-followup.json)。其他评测机需要重新校准。