题解：AT_abc360_e [ABC360E] Random Swaps of Balls

传送门

思路简介

不难想到，除了第个位置，在进行次操作后黑球到每个位置的概率是均等的。因此，我们只需要维护两个值：黑球在第个位置的概率和在其他位置的概率。

我们考虑从上一次操作进行完之后递推。令上一次操作完后在第一次的概率为，在其他位置的概率为。我们考虑如何得出在这一次操作完后的两种概率，记为和。

首先是在第一个位置的概率，有两种转移方式：

1. 从其他位置转移而来，对于每个除以外的位置，在种可能的数字中都有种方式转移。
2. 在这个位置保持不变，在所有的种可能性中，除了从其他位置转到号位置，其余的可能都是保持不变，有种方式。

然后是在其他位置的概率，有三种转移方式：

1. 从第个位置转移而来，在种可能性中有种组合能做到这一点。
2. 从除了第个位置和当前位置转移而来，对于剩下的个位置，每个位置有种组合来转移。
3. 在当前位置保持不变，有种组合可以做到这一点。

因此，我们可以得出：

直接递推即可。

代码

赛时提交记录