Egg Roulette
Contest: MemSQL Start[c]UP 3.0 - Round 2 (onsite finalists)
Difficulty rating: 3300
Tags: bitmasks, brute force, divide and conquer, math, meet-in-the-middle

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?

Input format:
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', '?'.

Output format:
Print the number of valid orderings that minimize unfairness and match S.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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".

Example input:
1 1
??BB

Example output:
0

Example input:
2 4
?BA??B??A???

Example output:
1

Editorial:
We can permute any prefix of an ordering containing at most R - 1 'A's or R - 1 'B's without changing the unfairness. This is because within that prefix one of the players cannot lose the game. This means that every ordering there is a unique ordering with the same unfairness that begins with exactly R - 1 'A's followed by R - 1 'B's and can be obtained by permuting such a prefix. Let's call this the canonical form of an ordering.
To search for canonical forms, we need to consider the remaining 2 * (C + 1) turns. The constraints set this to at most 42, so we can split it into two halves, compute every possible ordering for the left C + 1 turns and right C + 1 turns, then use a meet-in-the-middle algorithm to find those that minimize unfairness.
For each ordering in each half, we also need to compute how many corresponding orderings match the given string S. For the right half this is easy - every ordering either matches once or not at all. For the left half we have to consider non-canonical orderings. To compute this, we first need to find the longest prefix of the ordering that can be permuted. This is the longest prefix where every turn is the same as the first turn. Then we need to count how many 'A' and 'B' characters are in the ordering within that prefix, and how many 'A' and 'B' characters are in S within that prefix. If there are more 'A' or 'B' characters in S than the ordering, there are zero matches, otherwise the number of matches is given by a binomial coefficient.
The total runtime is O(C * 2C).