# 随机分析：概率

## 解法与署名

首选按数值建立指示变量，再使用全局仿射更新。程序：[std.cpp](std.cpp)。Codex（GPT-6）将期望递推应用到同值元素的指示变量，并给出 $O(n^2)$ 轮次处理与重复值合并的证明。

出题人的逐元素位置概率递推同样适用，完整说明见[逐元素概率转移](solution-alternative-element-probabilities.zh.md)，程序为 [alternative-element-probabilities.cpp](alternative-element-probabilities.cpp)。Codex（GPT-6）在该递推之后按数值累加贡献，形成矩阵输出。

## 概率是指示变量的期望

固定一个数值 $v$ .把当前位置值等于 $v$ 的事件记为指示变量：相等时为 $1$ ，否则为 $0$ .这些指示变量与卡片一起交换，因此它们的期望在结束时就是矩阵的第 $v$ 列。

初始系数为 $b_i=[a_i=v]$ .若 $v$ 出现 $c_v$ 次，指示变量的总和始终为 $c_v$ ，故平均值为 $\mu=c_v n^{-1}$ .一个值出现多次时自然合并到同一列；没有出现的值具有全零初始状态，最终仍全零。

## 单轮递推

模数记为 $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$ 即得到结果。

## 构造矩阵与复杂度

枚举 $v=1,\ldots,n$ ，每次建立长度为 $n$ 的初始指示数组，运行 $n$ 轮并将结果写入矩阵第 $v$ 列。两次模逆元计算在所有列之间共用。

总时间 $O(n^2+\log M)$ ，包括 $n^2$ 个输出。当前实现按列计算、按行输出，存储完整矩阵，空间 $O(n^2)$ .在固定模数的算术模型下，输出本身就需要 $\Omega(n^2)$ 时间，首选方案达到该阶。

逐元素转移为 $O(n^3+\log M)$ 时间、$O(n^2)$ 空间，是正确的备用方案。其单个元素的概率分布为滚动数组，矩阵需要保存。它更直接展示“原位置的元素最终去了哪里”；首选方案则直接计算题目需要的数值列。

## 分母、守恒与数值

所有 $n^n$ 个随机选择序列等概率，因此所有结果可以使用分母 $n^n$ ，它在 $n<M$ 时可逆。使用 64 位中间乘积，每步取模。

每行概率和为 $1$ .第 $v$ 列的概率和为输入中的出现次数 $c_v$ ，一般不为 $1$ .最后一行等于 $c_v/n$ ，因为最后一轮把一个均匀选择的位置换到位置 $n$ .这些恒等式也用于验证。

矩阵按行加权可得到[期望版](../shuffle-expectation/statement.zh.md)的结果：$E_i=\sum_{v=1}^{n}vP_{i,v}$ .

## 验证与使用

固定种子的正式输入配方见 `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.035418 | 5.99 | 已测输入通过 |
| [逐元素概率转移](alternative-element-probabilities.cpp) | 0.059872 | 6.01 | 已测输入通过 |

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