← 返回题目列表

AtCoder · arc201_c

C. 前缀覆盖

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

分数: 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