分数: 600 点
问题陈述
一个非空字符串,其中每个字符都是 A or B 被称为 AB 字符串
由 AB 字符串组成的.
一套 正整数的 X 称为 好套装 当满足以下条件时:
- 每个长度为 AB 的字符串 10^{100} 有一些元素 X 作为前缀。
为您提供了不同的 AB 字符串 S_1, S_2, \ldots, S_N。对于每个 k=1,2,\ldots,N,求模数 998244353,该集合的子集 \lbrace S_1,S_2,\ldots,S_k\rbrace 都是很好的套装。
约束
- 1\leq N\leq 2\times 10^5
- S_1, S_2, \ldots, S_N 是不同的 AB 字符串。
- \sum_{1\leq i\leq N}|S_i|\leq 5\times 10^5
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N
输出
输出 N 行。的 k- 第行应包含数字,模数 998244353,该集合的子集 \lbrace S_1,S_2,\ldots,S_k\rbrace 都是很好的套装。
示例输入 1
6 A B BA BB AA AB
示例输出 1
0 1 2 5 10 25
- 对于 k=1:没有好的子集。
- 对于 k=2:有 1 好的子集: \lbrace S_1,S_2\rbrace.
- 对于 k=3:有 2 好的子集: \lbrace S_1,S_2\rbrace, \lbrace S_1,S_2,S_3\rbrace.
- 对于 k=4:有 5 好的子集: \lbrace S_1,S_2\rbrace, \lbrace S_1,S_2,S_3\rbrace, \lbrace S_1,S_2,S_4\rbrace, \lbrace S_1,S_3,S_4\rbrace, \lbrace S_1,S_2,S_3,S_4\rbrace.
示例输入 2
10 A B AABA AABB AB AA AAA BB AAB BA
示例输出 2
0 1 2 4 8 20 41 82 170 425