随机分析：期望¶

解法与署名¶

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

保留出题人的逐元素概率转移及程序，也保留配套讲解中的直接期望递推及程序。两种基础解法均正确；首选方案减少了每轮逐位置更新的工作。

模数记为 \(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\) 的增长是线性的。

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

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

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

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

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

省略 --std 仅生成输入；--case 01 选择指定用例。独立验证见 check_r15_followup.py，五轮计时、内存与哈希见测量记录，环境见评测说明。

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

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

程序与算法	最慢中位数（秒）	峰值（MiB）	0.5 秒参考时限
全局仿射维护	0.030652	5.31	已测输入通过
直接期望递推	0.032607	5.33	已测输入通过
逐元素概率转移	0.054410	5.32	已测输入通过

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