← 返回题目列表

Codeforces · 1784/E

E. 无限游戏

中文机器翻译题面 查看原题

Alice 和 Bob 正在玩一个由集合组成的无限游戏。每组由回合组成。在每一轮中,一名玩家获胜。在一组比赛中第一个赢得两轮比赛的选手赢得该组比赛。因此,一组比赛总是以其中一名选手的得分 $$$2:0$$$ 或 $$$2:1$$$ 结束。

让我们将游戏场景称为由字符“a”和“b”组成的有限字符串$$$s$$$。考虑由字符串 $$$s$$$ 的重复组成的无限字符串: $$$sss \ldots$$$ 假设 Alice 和 Bob 根据这个无限字符串从左到右玩回合。如果字符串 $$$sss \ldots$$$ 中的一个字符是 'a',那么 Alice 赢得了这一轮;如果是“b”,鲍勃就赢得了这一轮。一旦其中一名球员赢得两轮比赛,该盘比赛就以对他们有利的方式结束,并从下一轮开始新的一盘比赛。

让我们将 $$$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 来说是胜利。

给定一个字符串 $$$s$$$,由字符 'a'、'b' 和 '?' 组成。考虑替换每个“?”的所有可能方法与 'a' 或 'b' 一起获取仅由字符 'a' 和 'b' 组成的字符串。计算其中有多少个导致 Alice 获胜的场景,有多少个导致平局的场景,以及有多少个导致 Bob 获胜的场景。打印这三个数字对 $$$998\,244\,353$$$ 取模。

输入

唯一一行包含单个字符串 $$$s$$$ ($$$1 \le |s| \le 200$$$),由字符“a”、“b”和“?”组成。

输出

打印三个整数:有多少种方式导致 Alice 赢得场景,有多少种方式导致平局,以及有多少种方式导致 Bob 场景获胜,以 $$$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

注意

第一个例子中,有四种方法来替换问号:

- $$$s = \mathtt{aa}$$$:Alice 赢得每盘 $$$2:0$$$ — 该场景是 Alice 获胜;
- $$$s = \mathtt{ab}$$$:Alice 和 Bob 轮流获胜,得分为 $$$2:1$$$ — 双方打平;
- $$$s = \mathtt{ba}$$$:Bob 和 Alice 轮流获胜,得分为 $$$2:1$$$ — 双方打平;
- $$$s = \mathtt{bb}$$$:鲍勃赢得每盘 $$$2:0$$$ — 该场景是鲍勃获胜。