Prefix Covering

AtCoder

IDarc201_c

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

6
A
B
BA
BB
AA
AB

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

Input #2

10
A
B
AABA
AABB
AB
AA
AAA
BB
AAB
BA

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Prefix Covering",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc201_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A non-empty string where every character is `A` or `B` is called an **AB string**.\nA set $X$ consisting of AB strings is called a **good set** when it satisfies the following:\n\n*   Every AB string of ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments