\[\prod_{i=1}^{k} \frac{1}{1-\rho_ix}=\sum_{i=1}^{k}\frac{a_i}{1-\rho_ix} \]

\[1=\sum_{i=1}^{k}a_i\prod_{j\ne i}(1-\rho_jx) \]

将 $ x = \frac{1}{\rho_n} $ 代入

\[1 = a_n\prod_{j\ne n}(1-\frac{\rho_j}{\rho_n}) \]

\[a_n = \frac{1}{\prod_{j\ne n}(1-\frac{\rho_j}{\rho_n})} \]

\[= \frac{\rho_n^{k-1}}{\prod_{j\ne n}(\rho_n-\rho_j)} \]

\[[x^n]\prod_{i=1}^{k} \frac{1}{1-\rho_ix}=\sum_{i=1}^{k}a_i\rho_i^n \]

\[= \sum_{i=1}^{k}\frac{\rho_i^{n+k-1}}{\prod_{j\ne i}(\rho_i-\rho_j)} \]

考虑 $ B $ 这个数经过 $ m $ 轮变成 $ A $ 的概率

\[[x^{m-1}]\frac{1}{B+1}\prod_{i=A}^{B}\frac{1}{1-\frac{1}{i+1}x} \]

\[= \frac{1}{B+1} \sum_{i=A}^{B}\frac{(\frac{1}{i+1})^{m+B-A-1}}{\prod_{j\ne i}(\frac{1}{i+1}-\frac{1}{j+1})} \]

\[= \frac{1}{B+1} \sum_{i=A}^{B}\frac{(\frac{1}{i+1})^{m+B-A-1}}{\prod_{j\ne i}(\frac{j-i}{(i+1)(j+1)})} \]

\[= \frac{1}{B+1} \sum_{i=A}^{B}\frac{(\frac{1}{i+1})^{m-1}}{\prod_{j\ne i}(\frac{j-i}{j+1})} \]

\[= \frac{1}{B+1} \frac{(B+1)!}{A!}\sum_{i=A}^{B}\frac{1}{i+1}\frac{(\frac{1}{i+1})^{m-1}}{\prod_{j\ne i}(j-i)} \]

\[= \frac{B!}{A!}\sum_{i=A}^{B}\frac{(\frac{1}{i+1})^m}{(i-A)!\cdot-1^{i-A}\cdot(B-i)!} \]

最终变为 A 这个数的概率是

\[\sum_{B=A}^{n} \frac{B!}{A!} p_{B} \sum_{i=A}^{B}\frac{(\frac{1}{i+1})^m}{(i-A)!\cdot-1^{i-A}\cdot(B-i)!} \]

发现直接算不好算，我们先计算 B 到 $ i $ 的贡献，再把贡献算到 A 上

\[\frac{1}{A!}\sum_{B=A}^{n} B! \cdot p_{B} \sum_{i=A}^{B} (\frac{1}{i+1})^m\cdot\frac{1}{(i-A)!\cdot-1^{i-A}}\cdot\frac{1}{(B-i)!} \]

定义 $ f_i $ 表示 $ i $ 之后所有的 B 对 $ i $ 的贡献，可以得到

\[f_i = (\frac{1}{i+1})^m\sum_{B=i}^{n} B!\cdot p_B \frac{1}{(B-i)!} \]

容易发现这是卷积的形式，然后就可以轻松得出变成 A 的概率

\[ans_A = \frac{1}{A!} \sum_{i=A}^{n} \frac{1}{(i-A)!\cdot -1^{i-A}} \]

仍然是卷积的形式