分数游戏（困难版）题解

思路

令 $f(n,m)$ 表示 $k=1$ 时的最优最终分数。Alice 在一回合中平衡 Bob 选择加法和减法后的两个结果，可得到相邻状态取平均值的递推。困难版不能存下完整的二维状态表，需要把递推化为组合数公式。

做法

子任务 1

当 $n\le20$ 时，不记忆化地展开 Bob 每回合的两种选择。边界为 $f(n,0)=0$ 和 $f(n,n)=n$，内部状态递归计算两个后继的平均值，复杂度为 $O(2^n)$。

子任务 2

按回合数从小到大计算

使用滚动数组后，每组复杂度为 $O(nm)$，在 $\sum n\le2000$ 时可以通过。

满分算法

记相邻差分 $d(n,m)=f(n,m)-f(n,m-1)$。由递推可证明

再次对 $m$ 求前缀和，得到

预处理阶乘、逆阶乘和二的逆幂，即可在 $O(m)$ 时间回答一组询问。因为 $m\le n$ 且所有测试组的 $\sum n\le10^6$，总循环次数也是 $O(10^6)$。最终答案乘以 $k$。

正确性证明

在内部状态 $0<m<n$，设 Alice 当前选择 $x$。Bob 选择加法后的值为

选择减法后的值为

Alice 的最优选择令两式相等，因此状态值恰为两个后继状态的平均值。边界 $m=0$ 时 Alice 只能保证零；边界 $m=n$ 时 Bob 每回合都必须加，Alice 每回合选择一，故值为 $n$。于是上述递推正确。

由递推对相邻 $m$ 作差，并结合帕斯卡恒等式，可归纳得到 $d(n,m)$ 的二项式前缀和表达式。再把 $d(n,1),\ldots,d(n,m)$ 相加，每个 $\binom ni$ 恰出现 $m-i$ 次，便得到满分公式。因此算法输出 $k f(n,m)$，正是原游戏的最优最终分数。

复杂度

预处理时间和空间均为 $O(N)$，其中 $N=\max n$。所有询问的总时间复杂度为 $O(N+\sum m)$，空间复杂度为 $O(N)$。