P9169 [省选联考 2023] 过河卒

考察两个红点一个黑点，状态数为 \(10^6\) 级别，那么对于这些结点分为以下几类：

• 不合法状态。
• 当前手必败态。
• 未确定状态。

根据博弈论知识，可以拓扑排序知道每个结点当前手到底是必胜态还是必败态：

• 若一个结点的拓展结点全是必胜态，则这个点为必败态。
• 若一个结点的拓展结点有一个是必败态，则这个点为必胜态。

至于中间需要最优化的过程，不过就是在拓扑排序的过程中最优化一些量而已，实际上这些量都是固定的可以被求出来的，代码比较难写。