P9316 [EGOI 2021] Double Move / 二选一游戏

Day 2 Problem D. 题面译自 [EGOI2021 doublemove](https://stats.egoi.org/media/task_description/2021_doublemove_en.pdf)。

爱丽丝和鲍勃在玩游戏，克莱尔在帮助他们。共有 $n$ 颗石子，编号从 $1$ 到 $n$。游戏分为三个阶段。 在第一阶段，爱丽丝和鲍勃轮流操作，爱丽丝先手。在每次操作中，玩家宣布他们要拿的石头，但不直接说出拿哪一个，而是给出两个选项。两个选项可能是相同的。也有可能说出已经说过的石头。第一阶段不取石子——玩家只是宣布他们在第二阶段的意图。第一阶段在宣布 $n+1$ 次后结束。 下面是 $n=3$ 的第一阶段的例子： 1. 爱丽丝：“我会取走 $1$ 或 $3$” 2. 鲍勃：“我会取走 $2$ 或 $2$” 3. 爱丽丝：“我会取走 $3$ 或 $2$” 4. 鲍勃：“我会取走 $1$ 或 $3$” 在第二阶段，对于 $n+1$ 次宣布的每一个，克莱尔用说“前者”或“后者”的方式从两个选项中选择一个。我们称克莱尔做出的 $n+1$ 次选择的序列为一个*方案*。可以发现，恰好有 $2\cdot 2\cdot 2\cdot\cdots\cdot 2=2^{n+1}$ 种可能的方案。（即使在一些宣布中，两个选项是完全相同的，我们认为“前者”“后者”选择不同为不同的方案。） 下面是克莱尔可能选择的 $16$ 种方案之一： 1. “前者”：爱丽丝将取 $1$。 2. “前者”：鲍勃将取 $2$。 3. “后者”：爱丽丝将取 $2$。 4. “前者”：鲍勃将取 $1$。 在第三阶段，爱丽丝和鲍勃根据克莱尔的选择开始取石子。第一个无法做出要求的操作的人——因为那个石子已经被取走——输掉游戏。注意到有 $n$ 个石子和 $n+1$ 次操作，一个玩家必然最终输掉游戏。 在上面的例子中，爱丽丝先取走 $1$。鲍勃接着取走 $2$。爱丽丝希望继续取走 $2$，但它已经被取走了，所以爱丽丝输掉了游戏，鲍勃因此获胜。 你已知整数 $n$，和第一阶段某一时刻的游戏状态：一个长度为 $k$ 的已经做出的宣布序列。这些宣布可以是完全随意的。 从此时开始，爱丽丝和鲍勃会以最优方式玩游戏，也就是说： 无论爱丽丝和鲍勃怎么玩，克莱尔都均匀随机地从 $2^{n+1}$ 种可能的方案中选择一个。爱丽丝和鲍勃知道这一点，因此当以最优方式玩游戏时，他们都尽力最小化他们输的方案数。 假设爱丽丝和鲍勃会按照上面描述的方式继续游戏。请分别求出两个人赢得游戏的方案数。

第一行两个整数 $n,k$：石头数和已经做出的宣布数。 接下来 $k$ 行，每行按照顺序描述一次宣布。每行两个整数：两个石头的编号（在 $1\sim n$ 且不一定不同）。 注意到当 $k < n+1$ 时，下一个做出宣布的玩家由 $k$ 的奇偶性决定。

一行，两个整数：爱丽丝赢的方案数、鲍勃赢的方案数，假设他们都按照上面描述的方式继续玩游戏。 注意到这两个整数的和应当为 $2^{n+1}$。

**样例 $1$ 解释** 这个样例与【题目描述】中给出的相同。不需要做出更多的宣布了，因此我们只需要计算多少种方案会导致爱丽丝赢，多少种方案会导致鲍勃赢。爱丽丝赢当且仅当克莱尔在第一步选择了 $1$，且在第三步选择了 $3$。其他方案都会导致爱丽丝输。 --- **样例 $2$ 解释** 如果爱丽丝先宣布 $(1,1)$，鲍勃会宣布 $(2,2)$，无论爱丽丝接下来宣布什么，她都会输，因为克莱尔会在第一步选择 $1$，在第二步选择 $2$，第三步就没有剩下的石头给爱丽丝取了。然而，这不是爱丽丝第一步的最优方案：她应该首先宣布 $(1,2)$。然后，无论鲍勃和爱丽丝在后两步如何宣布，他们都会赢 $8$ 种方案中的 $4$ 种。 --- **数据范围** 对于全部数据，$1\le n\le 35$，$0\le k\le n+1$。 - 子任务一（$15$ 分）：$n\le 4$。 - 子任务二（$34$ 分）：$n\le 10$。 - 子任务三（$20$ 分）：$n\le 25$。 - 子任务四（$10$ 分）：$k=0$。 - 子任务五（$21$ 分）：无特殊限制。