题解

思路

状态与边界

记 $f_{i,j}$ 为轮到当前玩家行动、当前玩家有 $i$ 张牌、对手有 $j$ 张牌时，当前玩家在最优策略下的胜率。牌的名字具有对称性，因此状态只与两人的牌数有关。

若 $i=0$，当前玩家只可能在对手的 $j$ 张牌和桌牌中猜测，故 $f_{0,j}=1/(j+1)$。若 $j=0$，当前玩家知道唯一未知牌就是桌牌，故 $f_{i,0}=1$。

做法

一个状态中的矩阵博弈

当前玩家询问时，只需考虑两类不可区分的动作：询问自己手中的牌来欺骗对手，或询问自己不知道的牌。对手在听到一次否定回答后，也只需决定相信或不相信。令

四个量依次构成双方两个纯策略下当前玩家的收益矩阵。若当前玩家以概率 $p$ 选择第一行，混合策略均衡要求对手两列的期望收益相同：

所以

两项依赖的下标和都为 $i+j-1$，因此可以按 $i+j$ 递增计算。

复杂度

三个算法层级

子任务 1 直接按上述博弈递归展开，不记忆任何状态，时间复杂度为 $O(2^{m+n})$，空间复杂度为 $O(m+n)$。

子任务 2 记忆每个 $(i,j)$，每个状态只计算一次，时间与空间复杂度均为 $O((m+n)^2)$。

满分算法按对角线滚动。计算和为 $s$ 的状态时只保留和为 $s-1$ 的整条对角线；对 $(i,j)$，所需两项分别是上一层下标 $j-1$ 与 $j$。时间复杂度为 $O((m+n)^2)$，空间复杂度降为 $O(m+n)$。

正确性证明

边界由玩家可辨认的未知牌集合直接得到。对内部状态，牌名的对称性把所有有效行动归并成收益相同的两类，任何同类动作都不会提供额外信息。零和二乘二矩阵博弈的混合策略均衡使对手对两列无差异，上式给出的 $p$ 及收益因此就是该状态的最优胜率。转移只依赖总牌数更少的状态，按总牌数归纳即可证明所有 $f_{i,j}$ 均正确。最终输出 $f_{m,n}$ 与 $1-f_{m,n}$。