/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
どの文字も A または B であるような空でない文字列を AB 文字列と呼ぶことにします。
AB 文字列からなる集合 X が次を満たすとき、良い集合であるということにします。
- 長さ 10^{100} であるような AB 文字列は必ずある X の要素を接頭辞に持つ。
相異なる AB 文字列 S_1, S_2, \ldots, S_N が与えられます。各 k=1,2,\ldots,N について、集合 \lbrace S_1,S_2,\ldots,S_k\rbrace の部分集合であって良い集合であるものの個数を 998244353 で割った余りを求めて下さい。
制約
- 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 行目には、集合 \lbrace S_1,S_2,\ldots,S_k\rbrace の部分集合であって良い集合であるものの個数を 998244353 で割った余りを出力して下さい。
入力例 1
6 A B BA BB AA AB
出力例 1
0 1 2 5 10 25
- k=1 の場合：良い部分集合はありません。
- k=2 の場合：良い部分集合は \lbrace S_1,S_2\rbrace の 1 個です。
- k=3 の場合：良い部分集合は \lbrace S_1,S_2\rbrace, \lbrace S_1,S_2,S_3\rbrace の 2 個です。
- k=4 の場合：良い部分集合は \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 の 5 個です。
入力例 2
10 A B AABA AABB AB AA AAA BB AAB BA
出力例 2
0 1 2 4 8 20 41 82 170 425
Score : 600 points
Problem Statement
A non-empty string where every character is A or B is called an AB string.
A set X consisting of AB strings is called a good set when it satisfies the following:
- Every AB string of length 10^{100} has some element of X as a prefix.
You are given distinct AB strings S_1, S_2, \ldots, S_N. For each k=1,2,\ldots,N, find the number, modulo 998244353, of subsets of the set \lbrace S_1,S_2,\ldots,S_k\rbrace that are good sets.
Constraints
- 1\leq N\leq 2\times 10^5
- S_1, S_2, \ldots, S_N are distinct AB strings.
- \sum_{1\leq i\leq N}|S_i|\leq 5\times 10^5
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Output N lines. The k-th line should contain the number, modulo 998244353, of subsets of the set \lbrace S_1,S_2,\ldots,S_k\rbrace that are good sets.
Sample Input 1
6 A B BA BB AA AB
Sample Output 1
0 1 2 5 10 25
- For k=1: There are no good subsets.
- For k=2: There is 1 good subset: \lbrace S_1,S_2\rbrace.
- For k=3: There are 2 good subsets: \lbrace S_1,S_2\rbrace, \lbrace S_1,S_2,S_3\rbrace.
- For k=4: There are 5 good subsets: \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.
Sample Input 2
10 A B AABA AABB AB AA AAA BB AAB BA
Sample Output 2
0 1 2 4 8 20 41 82 170 425