ABC380F 题解

为了方便，下面称 Takahashi（先手）为 A，Aoki（后手）为 B。

看到数据很小，可以接受指数级的时间复杂度，这启示我们往爆搜或状压的方向去想。

总结题意可以发现：一张牌只有三个去处：要么在 A 手上，要么在 B 手上，要么在桌上。因此我们用每张牌的状态来表示一个游戏局面 S，代码实现上可以用三进制状压。下面考虑 dp 的具体实现。

记 f(S) 表示游戏局面为 S，且轮到 A 时，A 是否必胜。类似地，记 g(S) 表示游戏局面为 S，且轮到 B 时，B 是否必胜。这里必须分别设轮到 A 和轮到 B 的状态，因为两人的手牌状态不同，能做的决策也不同。这样 dp 的总状态数为 2 \times 3^{N + M + L}，可以接受。

• 初始化：注意到一个玩家会输，当且仅当轮到他时他手上没有牌了，因此初始化“某人手上没有牌且轮到此人”的状态为必败状态。
• 转移：如果当前局面为 S，定义玩家操作后的后继局面为 S'。我们可以直接暴力枚举出哪张牌以及拿哪张牌，得到所有可能的 S'。在这些 S' 中，如果有一个使得轮到对手时对手必输，那么他总可以选择达到这个后继状态，因此对于他来说 S 是必胜状态。反之，S 对他就是必败状态。
• 答案统计：记游戏的初始局面为 S_0，若 f(S) = 1，则 A 胜，否则 B 胜。

如果你现在就开始兴致冲冲地写代码，你很快会发现一个问题：虽然我们已经有转移方程了，但我们该以什么顺序转移呢？甚至，这样 dp 究竟能否被转移？它有没有可能是有后效性的？可能很多人直接写个记忆化搜索就跑路了，但我认为这个问题还是值得研究的。

（以下分隔线内的内容选读）

一句话概括：每个人手牌上数字的和单调减小，所以每个状态最多被计算一次。

不妨先想想有的状压 dp 为什么可以转移。ABC354E 是一道和本题类似的打牌问题，但区别在于，玩家只能从桌上拿牌，而不能往桌面上放牌。如果记桌面上牌的集合为 s，拿走了牌之后的状态为 s'，把它们状压成整数，那么显然有 s' < s——因为拿走牌的操作就相当于把 s 的两个二进制位从 1 变成 0。这样，我们就可以简单地从小到大枚举状态来转移。

但这样解释没有触及到更本质的东西。如果我们把 dp 中的状态看作图中的节点，而状态之间的依赖关系看作有向边（即，如果状态 i 要从状态 j 转移过来，那么连一条 j \to i 的边）。那么，dp 的无后效性体现在转移图\ ^{*}上就是没有环，即转移图是 DAG，而 dp 的转移过程就相当于在转移图上做拓扑排序。如果我们要证明 dp 具有无后效性，就相当于要证明转移图上没有环。而在 ABC354E 这道题中，s' 和 s 满足 s' \sub s，而真包含关系是不会形成环的，因此可以转移。