#P17903. Random Shuffle
Random Shuffle
有长度为 的数组 ,第 个元素的得分为 。Alice 先手,随后与 Bob 交替操作。
每轮操作如下。设当前剩余数组长度为 :
- 将当前 复制为 ,再等概率地选择 个位置的一个排列,对 进行随机打乱。每次打乱独立进行;相等元素仍按各自位置参与打乱。
- 当前玩家观察 ,选择一个 ,要求 与 的前 个元素逐项相等。
- 删除 的前 个元素,获得这些元素的得分之和。选择 时不删除元素、不获得分数,仍结束本轮。
只有复制品 被打乱, 以及与其对应的得分始终保持原有相对顺序。剩余数组为空时游戏结束。双方都采取使自己期望总得分最大的策略,求 Alice 的期望得分。
另有 组对初始数组的修改。修改累积生效。需要对修改前、以及每组修改后的数组,分别求一次从完整数组重新开始游戏的答案。
输入格式
依次输入 、长度为 的数组 、长度为 的数组 、修改组数 ,各占一行。
每组修改先给出修改次数 ,接着 行,每行 表示令 。
范围:,,,,。同一组修改的位置满足 。
输出格式
输出 行,依次为初始状态和每组修改后的 Alice 期望得分。绝对误差或相对误差不超过 即可。
样例 1
输入
2
1 2
1 1
2
1
2 1 2
1
1 1 2
输出
1.333333333333
3.000000000000
4.000000000000
样例 2
输入
6
1 1 4 5 1 4
2 3 3 3 3 3
0
输出
9.013888888889