304544: CF865F. Egg Roulette

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Egg Roulette

题意翻译

给定 $R,C$ 表示有 $2R$ 个生鸡蛋和 $2C$ 个熟鸡蛋,我们将这些鸡蛋随机排布成一个排列。 Alice 和 Bob 在玩游戏,每次他们会在一个人的脑袋上按顺序打一个鸡蛋,如果一个人的脑袋上碎了 $R$ 个生鸡蛋,他就输了。 一般的情况下,我们总是轮流操作,然而这不公平,因为按照 Alice,Bob,Alice,Bob 的顺序执行,后手获胜的概率总是大一些。 我们定义一个操作顺序的不公平度,为两者获胜的概率的差值的绝对值,定义一个操作序列是公平的,当且仅当其不公平度是所有可能的操作序列的最小值。 Alice 和 Bob 想要研究有多少种公平的操作序列,然而这不够,他们给定了一个序列 $S$,其中部分位置已经填好了 A/B 表示这一位由 Alice 或 Bob 进行操作,其余位为 ```?```,你需要求有多少种填补此序列的方案,使得其是公平的。 $R,C\le 20,R+C\le 30$

题目描述

The game of Egg Roulette is played between two players. Initially $ 2R $ raw eggs and $ 2C $ cooked eggs are placed randomly into a carton. The shells are left on so there is no way to distinguish a raw egg from a cooked egg. One at a time, a player will select an egg, and then smash the egg on his/her forehead. If the egg was cooked, not much happens, but if the egg was raw, it will make quite the mess. This continues until one player has broken $ R $ raw eggs, at which point that player is declared the loser and the other player wins. The order in which players take turns can be described as a string of 'A' and 'B' characters, where the $ i $ -th character tells which player should choose the $ i $ -th egg. Traditionally, players take turns going one after the other. That is, they follow the ordering "ABABAB...". This isn't very fair though, because the second player will win more often than the first. We'd like you to find a better ordering for the players to take their turns. Let's define the unfairness of an ordering as the absolute difference between the first player's win probability and the second player's win probability. We're interested in orderings that minimize the unfairness. We only consider an ordering valid if it contains the same number of 'A's as 'B's. You will also be given a string $ S $ of length $ 2(R+C) $ containing only 'A', 'B', and '?' characters. An ordering is said to match $ S $ if it only differs from $ S $ in positions where $ S $ contains a '?'. Of the valid orderings that minimize unfairness, how many match $ S $ ?

输入输出格式

输入格式


The first line of input will contain integers $ R $ and $ C $ $ (1<=R,C<=20,R+C<=30) $ . The second line of input will contain the string $ S $ of length $ 2(R+C) $ consisting only of characters 'A', 'B', '?'.

输出格式


Print the number of valid orderings that minimize unfairness and match $ S $ .

输入输出样例

输入样例 #1

1 1
??BB

输出样例 #1

0

输入样例 #2

2 4
?BA??B??A???

输出样例 #2

1

输入样例 #3

4 14
????A??BB?????????????AB????????????

输出样例 #3

314

说明

In the first test case, the minimum unfairness is $ 0 $ , and the orderings that achieve it are "ABBA" and "BAAB", neither of which match $ S $ . Note that an ordering such as "ABBB" would also have an unfairness of $ 0 $ , but is invalid because it does not contain the same number of 'A's as 'B's. In the second example, the only matching ordering is "BBAAABABABBA".

Input

题意翻译

给定 $R,C$ 表示有 $2R$ 个生鸡蛋和 $2C$ 个熟鸡蛋,我们将这些鸡蛋随机排布成一个排列。 Alice 和 Bob 在玩游戏,每次他们会在一个人的脑袋上按顺序打一个鸡蛋,如果一个人的脑袋上碎了 $R$ 个生鸡蛋,他就输了。 一般的情况下,我们总是轮流操作,然而这不公平,因为按照 Alice,Bob,Alice,Bob 的顺序执行,后手获胜的概率总是大一些。 我们定义一个操作顺序的不公平度,为两者获胜的概率的差值的绝对值,定义一个操作序列是公平的,当且仅当其不公平度是所有可能的操作序列的最小值。 Alice 和 Bob 想要研究有多少种公平的操作序列,然而这不够,他们给定了一个序列 $S$,其中部分位置已经填好了 A/B 表示这一位由 Alice 或 Bob 进行操作,其余位为 ```?```,你需要求有多少种填补此序列的方案,使得其是公平的。 $R,C\le 20,R+C\le 30$

加入题单

上一题 下一题 算法标签: