随机分析：逐元素概率转移¶
出题人的元素位置概率递推。Codex（GPT-6）使用滚动数组整理 C++17 实现。程序：alternative-element-probabilities.cpp。首选方案与比较见主解。
追踪一个原始元素¶
模数记为 \(M=998244353\) .
暂时用原下标区分所有元素，即使它们的值相同。固定原位置 \(s\) 的元素，令 \(q_j\) 为它当前位于位置 \(j\) 的概率。初始 \(q_s=1\) ，其他位置为零。
第 \(i\) 轮先保存 \(c=q_i\) .对 \(j\ne i\) ：该元素若原在 \(j\) ，有 \((n-1)/n\) 的概率保留；若原在 \(i\) ，有 \(1/n\) 的概率移入。这两个事件互斥，所以
\[
q'_j=(n-1)n^{-1}q_j+n^{-1}c\pmod M
\]
它最终位于本轮位置 \(i\) 的概率为
\[
q'_i=n^{-1}\sum_jq_j=n^{-1}
\]
因为这一个元素恰好位于某一个位置。上述论证对任何历史状态成立，逐轮归纳即可得到正确的终态分布。
合成答案¶
记该分布为 \(q_{s,j}\) ，对所有原始元素分别运行转移，然后累加 \(E_j=\sum_s a_s q_{s,j}\) .这正是最终数值的期望，由期望线性性可知，不需要不同元素的位置相互独立。
复杂度与取舍¶
每个原始元素进行 \(n\) 轮、每轮更新 \(n\) 个位置，总时间 \(O(n^3+\log M)\) .单元素概率使用 \(O(n)\) 滚动空间；累加的期望数组同为 \(O(n)\) ，故总空间为 \(O(n)\) .
该方案直接展示每个元素的去向，可以独立检查更快的递推。它是正确的备用计算程序；当前范围内的计时状态见主解。每轮使用保存的旧 \(c\) ，避免更新顺序污染概率。