Infinite Game

题意翻译

Alice 和 Bob 正在玩一个由集合组成的无限游戏。每组由多个回合组成。在每一轮比赛中，其中一名选手获胜。第一个在一盘比赛中赢得两轮比赛的球员赢得了这盘比赛。因此，一盘总是以 $2:0$ 或 $2:1$ 的比分结束，有利于其中一名球员。 让我们将游戏场景称为由字符 `a` 和 `b` 组成的有限字符串 $s$ 。考虑一个由字符串 $ s $ : $ sss \ldots $ 的重复组成的无限字符串…… 假设 Alice 和 Bob 按照这个无限字符串从左到右进行循环。如果字符串 $ sss \ldots $ 的这个字符是 `a` ，则 Alice 赢得这一轮；如果是 `b` ，则 Bob 赢得这一轮。一旦其中一名球员赢了两轮，这一盘就以他们的优势结束，下一轮开始新的一盘。 让我们将ai定义为在根据给定场景进行游戏时，Alice 在前 i 个集合中赢得的集合数。 让我们将 $a_i$ 定义为 Alice 在根据给定场景进行游戏时在前 $i$ 集合中赢得的集合数。我们还将 $r$ 定义为比率 $ \frac{a_i}{i} $ 的限制 $ i \rightarrow \infty $ 。如果 $ r > \frac{1}{2} $ ，我们将说场景 $s$ 中 Alice 获胜。如果 $ r = \frac{1}{2} $ ，我们将说场景 $s$ 双方平局。如果 $ r < \frac{1}{2} $ ，我们会说场景 $s$ 中 Bob 获胜。 现在给你一个由字符 `a` ，`b` ，和 `?` 组成的字符串，考虑替换每个 `?` 的所有可能方法使用 `a` 或 `b` 获取仅由字符 `a` 和 `b` 组成的字符串。统计它们中有多少次 Alice 赢得了比赛，有多少次平局，还有多少次 Bob 赢得了比赛。以 $998\ 244\ 353$ 为模输出这三个数字。 输入一行，包含一个字符串 $s$（ $ 1 \le |s| \le 200 $ ），由字符 `a` ，`b`，和 `?` 组成。 输出一行，三个整数，表示字符串中有多少次 Alice 赢得了比赛，有多少次平局，还有多少次 Bob 赢得了比赛。

题目描述

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 $ .

输入输出格式

输入格式

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

输出格式

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 $ .

输入输出样例

输入样例 #1

??

输出样例 #1

1
2
1

输入样例 #2

?aa?b

输出样例 #2

1
3
0

输入样例 #3

a???ba

输出样例 #3

4
3
1

输入样例 #4

????????

输出样例 #4

121
14
121

输入样例 #5

ba????a?a???abbb?

输出样例 #5

216
57
239

输入样例 #6

a????a??????b??abbababbbb?a?aaa????bb

输出样例 #6

97833
28387
135924

输入样例 #7

??????????????a????????????????b?????

输出样例 #7

484121060
448940322
484613337

说明

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.