CF865F Egg Roulette

蛋轮盘（Egg Roulette）是一款两名玩家参与的游戏。最初，有 $2R$ 个生鸡蛋和 $2C$ 个熟鸡蛋被随机放入一个蛋盒。由于鸡蛋壳都没有去掉，无法区分生蛋还是熟蛋。接下来，玩家轮流选择一个鸡蛋，然后将其砸在自己的额头上。如果鸡蛋是熟的，几乎没有什么影响；但如果是生的，则会变得相当狼狈。这个过程持续进行，直到某个玩家已经砸破了 $R$ 个生鸡蛋，该玩家即为失败者，另外一位玩家获胜。 轮到谁选择鸡蛋的顺序可以用一个只包含 'A' 和 'B' 的字符串表示，第 $i$ 个字符表示第 $i$ 步该由哪位玩家选蛋。传统上，玩家轮流选择，即顺序为 "ABABAB……"。但这种方式并不公平，因为第二位玩家获胜的概率更高。请你帮忙寻找一种更公平的轮流顺序。我们将一个顺序的不公平度定义为两位玩家获胜概率的绝对差值。现在我们关注不公平度最小的轮流顺序。我们只考虑当 'A' 和 'B' 的数量相同时的顺序是有效的。 你还会给定一个长度为 $2(R+C)$ 的字符串 $S$，只包含 'A'、'B' 和 '?' 字符。对于一个轮流顺序来说，只有在 $S$ 的相应位置为 '?' 时才能与 $S$ 不同。对于所有最小不公平度的有效顺序，问有多少个顺序与 $S$ 匹配？

输入的第一行为两个整数 $R$ 和 $C$，$1 \leq R, C \leq 20, R + C \leq 30$。 输入的第二行为长度为 $2(R+C)$ 且只包含 'A'、'B'、'?' 的字符串 $S$。

输出所有与 $S$ 匹配且不公平度最小的有效顺序的数量。

在第一个样例中，最小不公平度为 $0$，所有实现该不公平度的顺序是 "ABBA" 和 "BAAB"，但都不与 $S$ 匹配。注意，像 "ABBB" 这样的顺序不公平度虽然为 $0$，但无效，因为其中 'A' 和 'B' 的数量不相等。 在第二个样例中，唯一符合条件的顺序是 "BBAAABABABBA"。 由 ChatGPT 5 翻译