110 . Boundle

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (6/9)

Tags

ioicamp ioicamp-2023

Description

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

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

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

Input Format

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

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

  • 1≤N≤105
  • 所有詢問的字串皆不相同
  • 不存在一個答案字串滿足所有的回答

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 輪後結束：

  • {3}

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

  • {1,2}
  • {1,3}
  • {2,1}
  • {2,3}

Problem Source

IOICamp 2023 Day3 pB

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 1, 3~12 每個詢問字串的第五位皆為 A，每個回答字串的第五位皆為 =，且 N≤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
Submit
Back to Top