TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

62.5% (5/8)

Tags

Description

正常的 Wordle 太無聊了,於是你決定設計一種魔改版 Wordle 來給你的朋友玩。你的朋友每次會詢問一個長度 $5$ 且僅由大寫英文字母組成的字串,而你會回答一個長度為 $5$ 且僅由 >, =, < 組成的字串,假設答案為 $s$,詢問的字串為 $t$,則若回答的字串第 $i$ 項是 < 就代表 $s_i < t_i$,= 就代表 $s_i = t_i$,> 就代表 $s_i > t_i$。其中大小關係與字母的字典序相同,A 最小且 Z 最大。

經由事先調查,你已經知道你的朋友有 $N$ 個字串是他會問的,為了加速遊戲進行,你任意決定了每一個詢問的回答。不過,你很快就發現這些回答是矛盾的,也就是說其實不存在一個長度為 $5$ 的大寫英文字串滿足所有回答提供的不等式。於是,在你跟你的朋友開始玩這個遊戲前,你決定寫一個程式來模擬你的朋友的行為。程式每個回合都會從 $N$ 個字串中還沒有被選過的字串裡等機率隨機選一個作為詢問,如果此次的回答跟前面的回答矛盾(不存在長度為 $5$ 的大寫英文字串滿足所有不等式),程式就會在這輪結束。注意到你的程式並不在乎是否已經答對,程式只會在第一次發現當前所有回答矛盾時結束。因為保證了所有答案是矛盾的,所以所有詞都問完時程式一定會終結。

對每個從 $1$ 到 $N$ 的 $i$ ,求出這個程式恰在執行 $i$ 輪後結束的方法數,兩種方法不一樣當且僅當至少有一回合詢問的字串不一樣,輸出的數字對 $998244353$ 取模。

Input Format

輸入第一行有一個正整數 $N$。

接下來的 $N$ 行每行讀入兩個字串,第一個字串是長度為 $5$ 的大寫英文字串,第二個字串是長度為 $5$ 且僅由 >, =, < 組成的字串。代表一組詢問的字串與回答的字串。

  • $1 \leq N \leq 10^ 5$
  • 所有詢問的字串皆不相同
  • 不存在一個答案字串滿足所有的回答

Output Format

請輸出 $N$ 個數字於一行並以空格分開,第 $i$ 個數字代表程式恰在執行 $i$ 輪結束後的方法數,輸出的數字請對 $998244353$ 取模。

Sample Input 1

3
BVHUQ ><>><
YJCEQ <<><<
SXXWZ >>==>

Sample Output 1

1 4 0

Sample Input 2

8
IFSXA >><<=
ZAKDA <>=>=
UZVAA <<<>=
MTACA <>>>=
RJKVA <><<=
IOXOA >=<<=
MRMHA ><<<=
BYFWA ==<>=

Sample Output 2

0 16 108 396 816 720 0 0

Sample Input 3

8
BRKPR ><=<>
VUCTO <<=<=
PTCDB <<=>>
PHMGV <><><
FGWHD >><>>
SUSFH <<<<>
IOLDD <<<<>
WJPXX <><<<

Sample Output 3

0 14 120 444 744 360 0 0

Hints

在範例測資一中,只有 $1$ 種方法會在恰在執行 $1$ 輪後結束:

  • $\lbrace 3 \rbrace$

有 $4$ 種方法會在恰執行 $2$ 輪後結束:

  • $\lbrace 1, 2 \rbrace$
  • $\lbrace 1, 3 \rbrace$
  • $\lbrace 2, 1 \rbrace$
  • $\lbrace 2, 3 \rbrace$

Problem Source

IOICamp 2023 Day3 pB

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 1, 3~12 每個詢問字串的第五位皆為 A,每個回答字串的第五位皆為 =,且 $N \leq 5000$ 50
3 0~23 無特別限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 15000 524288 65536 1 3
1 15000 524288 65536 1 2 3
2 15000 524288 65536 1 3
3 15000 524288 65536 2 3
4 15000 524288 65536 2 3
5 15000 524288 65536 2 3
6 15000 524288 65536 2 3
7 15000 524288 65536 2 3
8 15000 524288 65536 2 3
9 15000 524288 65536 2 3
10 15000 524288 65536 2 3
11 15000 524288 65536 2 3
12 15000 524288 65536 2 3
13 15000 524288 65536 3
14 15000 524288 65536 3
15 15000 524288 65536 3
16 15000 524288 65536 3
17 15000 524288 65536 3
18 15000 524288 65536 3
19 15000 524288 65536 3
20 15000 524288 65536 3
21 15000 524288 65536 3
22 15000 524288 65536 3
23 15000 524288 65536 3