# 随机分析：逐元素概率转移

出题人的元素位置概率递推。Codex（GPT-6）使用滚动数组整理 C++17 实现，并将终态概率按元素数值累加为矩阵。程序：[alternative-element-probabilities.cpp](alternative-element-probabilities.cpp)。首选方案与比较见[主解](solution.zh.md)。

## 追踪一个原始元素

模数记为 $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}$ ，对每个原始元素，把 $q_{s,j}$ 加到矩阵条目 $P_{j,a_s}$ .位置 $j$ 在最终恰好容纳一个元素，因此不同原始元素占据该位置的事件互斥，同值元素的概率可以相加。矩阵的列是数值，不能直接把原下标当作列号。

## 复杂度与取舍

每个原始元素进行 $n$ 轮、每轮更新 $n$ 个位置，总时间 $O(n^3+\log M)$ .单元素概率使用 $O(n)$ 滚动空间；输出矩阵占 $O(n^2)$ ，故总空间为 $O(n^2)$ .

该方案直接展示每个元素的去向，可以独立检查更快的递推。它是正确的备用计算程序；当前范围内的计时状态见[主解](solution.zh.md#实测结果)。每轮使用保存的旧 $c$ ，避免更新顺序污染概率。