CF1784E Infinite Game

Alice 和 Bob 正在玩一个由若干局组成的无限游戏。每一局由若干轮组成，每一轮有一名玩家获胜。第一个赢得两轮的玩家将赢得该局。因此，每一局的最终比分总是 $2:0$ 或 $2:1$，胜者为 Alice 或 Bob。 我们称一个游戏场景为一个由字符 'a' 和 'b' 组成的有限字符串 $s$。考虑一个由 $s$ 无限重复拼接而成的无限字符串：$sss\ldots$。假设 Alice 和 Bob 按照这个无限字符串从左到右进行每一轮。如果当前字符为 'a'，则 Alice 赢得该轮；如果为 'b'，则 Bob 赢得该轮。当有一名玩家赢得两轮时，该局结束，下一局从下一个字符开始。 定义 $a_i$ 为 Alice 在前 $i$ 局中赢得的局数。定义 $r$ 为比值 $\frac{a_i}{i}$ 在 $i \rightarrow \infty$ 时的极限。如果 $r > \frac{1}{2}$，我们称场景 $s$ 对 Alice 有利；如果 $r = \frac{1}{2}$，称为平局；如果 $r < \frac{1}{2}$，称场景对 Bob 有利。 现在给定一个只包含 'a'、'b' 和 '?' 的字符串 $s$。请统计将所有 '?' 替换为 'a' 或 'b' 所有可能的方案中，有多少种方案使得场景对 Alice 有利，有多少种方案为平局，有多少种方案对 Bob 有利。请将这三个数对 $998\,244\,353$ 取模后输出。

一行一个字符串 $s$（$1 \le |s| \le 200$），仅包含字符 'a'、'b' 和 '?'。

输出三个整数，分别表示对 Alice 有利、平局、对 Bob 有利的方案数，对 $998\,244\,353$ 取模。

在第一个样例中，有四种替换问号的方式： - $s = \mathtt{aa}$：Alice 每局都以 $2:0$ 获胜——对 Alice 有利； - $s = \mathtt{ab}$：Alice 和 Bob 轮流以 $2:1$ 获胜——平局； - $s = \mathtt{ba}$：Bob 和 Alice 轮流以 $2:1$ 获胜——平局； - $s = \mathtt{bb}$：Bob 每局都以 $2:0$ 获胜——对 Bob 有利。 由 ChatGPT 4.1 翻译