正常的 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$ 取模。
輸入第一行有一個正整數 $N$。
接下來的 $N$ 行每行讀入兩個字串,第一個字串是長度為 $5$ 的大寫英文字串,第二個字串是長度為 $5$ 且僅由 >
, =
, <
組成的字串。代表一組詢問的字串與回答的字串。
請輸出 $N$ 個數字於一行並以空格分開,第 $i$ 個數字代表程式恰在執行 $i$ 輪結束後的方法數,輸出的數字請對 $998244353$ 取模。
在範例測資一中,只有 $1$ 種方法會在恰在執行 $1$ 輪後結束:
有 $4$ 種方法會在恰執行 $2$ 輪後結束:
IOICamp 2023 Day3 pB
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~2 | 範例測資 | 0 |
2 | 1, 3~12 | 每個詢問字串的第五位皆為 A ,每個回答字串的第五位皆為 = ,且 $N \leq 5000$ |
50 |
3 | 0~23 | 無特別限制 | 50 |