Infinite Game
Contest: VK Cup 2022 - Финальный раунд (Engine)
Difficulty rating: 3100
Tags: brute force, combinatorics, dp, games, probabilities

Alice and Bob are playing an infinite game consisting of sets. Each set consists of rounds. In each round, one of the players wins. The first player to win two rounds in a set wins this set. Thus, a set always ends with the score of $$$2:0$$$ or $$$2:1$$$ in favor of one of the players.

Let's call a game scenario a finite string $$$s$$$ consisting of characters 'a' and 'b'. Consider an infinite string formed with repetitions of string $$$s$$$: $$$sss \ldots$$$ Suppose that Alice and Bob play rounds according to this infinite string, left to right. If a character of the string $$$sss \ldots$$$ is 'a', then Alice wins the round; if it's 'b', Bob wins the round. As soon as one of the players wins two rounds, the set ends in their favor, and a new set starts from the next round.

Let's define $$$a_i$$$ as the number of sets won by Alice among the first $$$i$$$ sets while playing according to the given scenario. Let's also define $$$r$$$ as the limit of ratio $$$\frac{a_i}{i}$$$ as $$$i \rightarrow \infty$$$. If $$$r > \frac{1}{2}$$$, we'll say that scenario $$$s$$$ is winning for Alice. If $$$r = \frac{1}{2}$$$, we'll say that scenario $$$s$$$ is tied. If $$$r < \frac{1}{2}$$$, we'll say that scenario $$$s$$$ is winning for Bob.

You are given a string $$$s$$$ consisting of characters 'a', 'b', and '?'. Consider all possible ways of replacing every '?' with 'a' or 'b' to obtain a string consisting only of characters 'a' and 'b'. Count how many of them result in a scenario winning for Alice, how many result in a tied scenario, and how many result in a scenario winning for Bob. Print these three numbers modulo $$$998\,244\,353$$$.

Input format:
The only line contains a single string $$$s$$$ ($$$1 \le |s| \le 200$$$), consisting of characters 'a', 'b', and '?'.

Output format:
Print three integers: how many ways result in a scenario winning for Alice, how many result in a tied scenario, and how many result in a scenario winning for Bob, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first example, there are four ways to replace the question marks:

- $$$s = \mathtt{aa}$$$: Alice wins every set $$$2:0$$$ — the scenario is winning for Alice;
- $$$s = \mathtt{ab}$$$: Alice and Bob win sets in turns, with the score of $$$2:1$$$ each — the scenario is tied;
- $$$s = \mathtt{ba}$$$: Bob and Alice win sets in turns, with the score of $$$2:1$$$ each — the scenario is tied;
- $$$s = \mathtt{bb}$$$: Bob wins every set $$$2:0$$$ — the scenario is winning for Bob.

Example input:
??

Example output:
1
2
1

Example input:
?aa?b

Example output:
1
3
0

Editorial:
For a fixed game scenario $$$s$$$, let's build a weighted functional graph on $$$4$$$ vertices that correspond to set scores $$$0:0$$$, $$$1:0$$$, $$$0:1$$$, and $$$1:1$$$. For each score $$$x$$$, traverse the scenario from left to right, changing the score after each letter, and starting a new set whenever necessary. If the set score by the end of the scenario is $$$y$$$, add a directed edge from $$$x$$$ to $$$y$$$. The weight of this edge is the number of sets Alice wins during the process, minus the number of sets Bob wins.
When we have built such a graph for a game scenario $$$s$$$, we can easily decide whether $$$s$$$ is winning for Alice, tied, or winning for Bob. Starting from vertex $$$0:0$$$, move by the outgoing edges until you arrive at a cycle. In the cycle, find the sum the edge weights. If the sum is positive, the scenario is winning for Alice; if the sum is $$$0$$$, the scenario is tied; if the sum is negative, the scenario is winning for Bob.
Now we can use dynamic programming. Let $$$f(i, \{u_0, u_1, u_2, u_3\}, \{w_0, w_1, w_2, w_3\})$$$ be the number of ways to choose $$$s_1 s_2 \ldots s_i$$$ so that edges from vertices $$$0, 1, 2, 3$$$ go to vertices $$$u_0, u_1, u_2, u_3$$$ and have weights $$$w_0, w_1, w_2, w_3$$$, respectively. Even though this DP has $$$O(n^5)$$$ states, it might be possible to get this solution accepted if you only visit reachable states and optimize your solution's constant factor.
However, here's an idea that drastically improves the time complexity. Note that in the end, we are only interested in the sum of some $$$w_j$$$, and not in every value separately. Outside of our DP, let's fix the mask of vertices that will lie on the cycle reachable from $$$0:0$$$. In the DP state, we can just store the sum $$$s$$$ of $$$w_j$$$ over $$$j$$$ belonging to this mask: $$$f(i, \{u_0, u_1, u_2, u_3\}, s)$$$. In the end, we will look at the values of $$$u_0, u_1, u_2, u_3$$$ and check if the cycle in our graph is indeed the one we want; only if that's true, we will add the DP value to the overall answer.
This way, at the cost of running the DP $$$2^4$$$ times, we have cut the number of states to $$$O(n^2)$$$. The overall time complexity of this solution is $$$O(n^2)$$$ too, although the constant factor is huge.