随机分析：概率¶

解法与署名¶

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

出题人的逐元素位置概率递推同样适用，完整说明见逐元素概率转移，程序为 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\) .这些恒等式也用于验证。

矩阵按行加权可得到期望版的结果：\(E_i=\sum_{v=1}^{n}vP_{i,v}\) .

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

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