AGC006C Rabbit Exercise

题意：数轴上有 只兔子，编号为 ，第 只兔子的初始坐标为 。

兔子会以以下的方式在数轴上行动 ：一轮包含 次跳跃，第 次跳跃中，是兔子 从兔子 和兔子 中等概率的选一个。

（保证 ）

记选的兔子坐标为 ，那么 号兔子会跳到它当前坐标关于 的对称点。

（注意，即使兔子的位置顺序变化了，但是编号仍保持不变）

兔子会进行 轮跳跃，对每个兔子，求出它最后坐标的期望值。以实数的形式输出。

，。

---

点 关于 的对称点为 ，这是线性的，所以可以直接维护期望。

现在问题变为，每次给定 令 ，求将这组 个操作重复 轮，最终得到的 数组。

（不难发现答案其实一定是整数）

这里有三项，较为复杂。考虑差分，记 。

则每次操作后

实际上相当于交换了 与 。

记录这些交换构成的映射，接下来就是计算映射的 次复合，容易做到 。