题解

思路

固定剩余回合数和 Bob 仍被迫执行加法的次数。Alice 本回合选择 $x$ 后，Bob 的两种选择分别进入两个相邻状态。最优的 $x$ 会让两种结果相等，因此得到取平均值的动态规划。

做法

令 $f[n][m]$ 表示 $k=1$ 时的最优最终分数。若 $m=0$，Bob 可以永远做减法，Alice 只能保证零；若 $m=n$，Bob 每回合都必须加，故 $f[n][n]=n$。

对 $0<m<n$，加法后的未来值为 $x+f[n-1][m-1]$，减法后的未来值为 $-x+f[n-1][m]$。Alice 选择

使二者相等，于是

预处理所有状态，每组答案为 $k f[n][m]$。模意义下除以二等价于乘 $2^{-1}$。

子任务一可不记忆化地展开完整博弈递归。子任务二满足 $f[n][1]=2^{-(n-1)}$，可快速幂直接计算。

复杂度

预处理时间和空间复杂度均为 $O(N^2)$，每组询问为 $O(1)$。