2 . 苦無出鹿

Submit
Status
Ranklist
Back to Problems List

TopCoder

littlecube

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

33.3% (1/3)

Tags

ntucpc-challenge1

Description

虎視餡子使用苦無攻擊鹿乃子乃子

小鹿時裝週即將在幾天後開始進行，為了成為小鹿時裝週上的焦點，虎視虎子正與鹿乃子乃子在操場上進行訓練。而虎視餡子為了阻止兩人過於靠近，她聯合了馬車芽芽芽準備要一同阻止兩人的行動。

日野南高校的操場可以視為一個圓形，而虎視餡子在操場的外圍設置了 $N$ 臺的苦無機器人，機器人之間的距離相同，把操場分成 $N$ 段相等的圓弧部分。機器人以逆時針順序從 $1$ 到 $N$ 編號，而編號 $i$ 的機器人逆時針方向的操場部分編號為 $i$。虎視餡子與馬車芽芽芽會分別負責操控一些機器人，每臺機器人會恰好被其中一個人操控，但可能有其中一個人沒有操控任何機器人。

機器人一開始沒有任何的配對，而虎視餡子與馬車芽芽芽可以從還沒被配對的機器人之中，每次選擇兩臺自己負責的機器人進行配對，將其中一臺設為發射模式，另一臺設為接收模式。設定完成後，發射模式的機器人便會開始向接收模式的機器人發射苦無，並由接收模式的機器人回收這些苦無。機器人的使用數量沒有限制，但每一臺機器人只能與另一臺機器人配對，且無法將自己負責的機器人與另一個人負責的機器人配對。苦無發射的路線可以被視為連接操場圓周上兩個機器人所在位置的一條弦，為了避免飛行中的苦無互相干擾，無論機器人是否被同一個人控制，任意兩對機器人的苦無的發射路線皆不可相交。

虎視虎子與鹿乃子乃子兩人正在操場進行訓練，操場的每個部分都會被恰好其中一個人使用，但可能有其中一個人沒有使用任何一個部分。要穿越苦無發射的路線是很危險的，因此操場上被發射路線的弦隔開的兩段圓弧之間無法通行。為了隔開虎視虎子和鹿乃子乃子，虎視餡子希望把操場用發射路線的弦分隔後的每一段圓弧都只被其中一個人使用。

虎視餡子把機器人的分配及操場的使用合稱為一個「狀態」。綠色的圓，以字母 $\texttt{G}$ 表示，是馬車芽芽芽負責的機器人；紫色的圓，以字母 $\texttt{P}$ 表示，則是虎視餡子負責的機器人；黃色的區域，以字母 $\texttt{Y}$ 表示，為虎視虎子使用的操場部分，紅色的區域，以字母 $\texttt{R}$ 表示，則是鹿乃子乃子使用的操場部分。

舉例來說，以下是兩個被分成 $3$ 段的操場的狀態，

左邊的操場如果馬車芽芽芽將自己負責的兩臺機器人配對，便會將操場分隔成兩段圓弧，一段都是虎視虎子的部分，另一段則都是鹿乃子乃子的部分，故可以順利隔開兩人。右邊的操場則無論怎麼配對都無法隔開兩人。

然而，事情沒有想得那麼簡單。現在還有一部分的機器人還沒決定要給誰操控，也還有一部分的操場不確定是被誰使用。虎視餡子想知道，現在一共還有多少種可能的狀態，存在配對機器人的方式，使得被苦無分隔後的每一段圓弧都只被其中一個人使用。請你回答方法數除以 $998244353$ 的餘數。

Input Format

輸入的第一行為一整數 $N$。第二行為一長度為 $2N$ 的字串 $S$，表示機器人及操場的狀態。

  • $2 \leq N \leq 10 ^ 6$
  • 對於奇數 $i$，$S_i$ 表示第 $\frac {i+1} 2$ 部分的操場的狀態：
    • 若 $S_i = \texttt{Y}$，表示該部分的操場由虎視虎子使用。
    • 若 $S_i = \texttt{R}$，表示該部分的操場由鹿乃子乃子使用。
    • 若 $S_i = \texttt{?}$：表示不確定該部分由誰使用。
  • 對於偶數 $i$，$S_i$ 表示第 $\frac i 2$ 臺機器人的狀態：
    • 若 $S_i = \texttt{P}$，表示該機器人由虎視餡子操控。
    • 若 $S_i = \texttt{G}$，表示該機器人由馬車芽芽芽操控。
    • 若 $S_i = \texttt{?}$：表示該機器人還沒決定要給誰操控。

Output Format

輸出一行包含一個整數，表示還有多少種可能的狀態，存在配對機器人的方式，使得被苦無分隔後的每一段圓弧都只被其中一個人使用，除以 $998244353$ 後的餘數。

Sample Input 1

2
????

Sample Output 1

12

Sample Input 2

3
??YP?G

Sample Output 2

4

Sample Input 3

5
YGYPRGYPYG

Sample Output 3

0

Hints

第一筆範例測資中的 $12$ 種可能狀態如下圖，只有在操場的兩個部分由不同人使用，且兩個機器人由不同人操控時才無法隔開虎視虎子和鹿乃子乃子。

Problem Source

改編自 IOICamp 2023 Day4 pE - 孤獨搖滾

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~14 $N \leq 10 ^ 1$ 0.1
3 0~28 $N \leq 10 ^ 2$ 0.3
4 0~47 $N \leq 10 ^ 3$ 0.9
5 0~63 $N \leq 10 ^ 4$ 2.7
6 0~82 $N \leq 10 ^ 5$ 8.1
7 0~121 $N \leq 10 ^ 6$（無額外限制） 87.9

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 524288 65536 1 2 3 4 5 6 7
1 6000 524288 65536 1 2 3 4 5 6 7
2 6000 524288 65536 1 2 3 4 5 6 7
3 6000 524288 65536 2 3 4 5 6 7
4 6000 524288 65536 2 3 4 5 6 7
5 6000 524288 65536 2 3 4 5 6 7
6 6000 524288 65536 2 3 4 5 6 7
7 6000 524288 65536 2 3 4 5 6 7
8 6000 524288 65536 2 3 4 5 6 7
9 6000 524288 65536 2 3 4 5 6 7
10 6000 524288 65536 2 3 4 5 6 7
11 6000 524288 65536 2 3 4 5 6 7
12 6000 524288 65536 2 3 4 5 6 7
13 6000 524288 65536 2 3 4 5 6 7
14 6000 524288 65536 2 3 4 5 6 7
15 6000 524288 65536 3 4 5 6 7
16 6000 524288 65536 3 4 5 6 7
17 6000 524288 65536 3 4 5 6 7
18 6000 524288 65536 3 4 5 6 7
19 6000 524288 65536 3 4 5 6 7
20 6000 524288 65536 3 4 5 6 7
21 6000 524288 65536 3 4 5 6 7
22 6000 524288 65536 3 4 5 6 7
23 6000 524288 65536 3 4 5 6 7
24 6000 524288 65536 3 4 5 6 7
25 6000 524288 65536 3 4 5 6 7
26 6000 524288 65536 3 4 5 6 7
27 6000 524288 65536 3 4 5 6 7
28 6000 524288 65536 3 4 5 6 7
29 6000 524288 65536 4 5 6 7
30 6000 524288 65536 4 5 6 7
31 6000 524288 65536 4 5 6 7
32 6000 524288 65536 4 5 6 7
33 6000 524288 65536 4 5 6 7
34 6000 524288 65536 4 5 6 7
35 6000 524288 65536 4 5 6 7
36 6000 524288 65536 4 5 6 7
37 6000 524288 65536 4 5 6 7
38 6000 524288 65536 4 5 6 7
39 6000 524288 65536 4 5 6 7
40 6000 524288 65536 4 5 6 7
41 6000 524288 65536 4 5 6 7
42 6000 524288 65536 4 5 6 7
43 6000 524288 65536 4 5 6 7
44 6000 524288 65536 4 5 6 7
45 6000 524288 65536 4 5 6 7
46 6000 524288 65536 4 5 6 7
47 6000 524288 65536 4 5 6 7
48 6000 524288 65536 5 6 7
49 6000 524288 65536 5 6 7
50 6000 524288 65536 5 6 7
51 6000 524288 65536 5 6 7
52 6000 524288 65536 5 6 7
53 6000 524288 65536 5 6 7
54 6000 524288 65536 5 6 7
55 6000 524288 65536 5 6 7
56 6000 524288 65536 5 6 7
57 6000 524288 65536 5 6 7
58 6000 524288 65536 5 6 7
59 6000 524288 65536 5 6 7
60 6000 524288 65536 5 6 7
61 6000 524288 65536 5 6 7
62 6000 524288 65536 5 6 7
63 6000 524288 65536 5 6 7
64 6000 524288 65536 6 7
65 6000 524288 65536 6 7
66 6000 524288 65536 6 7
67 6000 524288 65536 6 7
68 6000 524288 65536 6 7
69 6000 524288 65536 6 7
70 6000 524288 65536 6 7
71 6000 524288 65536 6 7
72 6000 524288 65536 6 7
73 6000 524288 65536 6 7
74 6000 524288 65536 6 7
75 6000 524288 65536 6 7
76 6000 524288 65536 6 7
77 6000 524288 65536 6 7
78 6000 524288 65536 6 7
79 6000 524288 65536 6 7
80 6000 524288 65536 6 7
81 6000 524288 65536 6 7
82 6000 524288 65536 6 7
83 6000 524288 65536 7
84 6000 524288 65536 7
85 6000 524288 65536 7
86 6000 524288 65536 7
87 6000 524288 65536 7
88 6000 524288 65536 7
89 6000 524288 65536 7
90 6000 524288 65536 7
91 6000 524288 65536 7
92 6000 524288 65536 7
93 6000 524288 65536 7
94 6000 524288 65536 7
95 6000 524288 65536 7
96 6000 524288 65536 7
97 6000 524288 65536 7
98 6000 524288 65536 7
99 6000 524288 65536 7
100 6000 524288 65536 7
101 6000 524288 65536 7
102 6000 524288 65536 7
103 6000 524288 65536 7
104 6000 524288 65536 7
105 6000 524288 65536 7
106 6000 524288 65536 7
107 6000 524288 65536 7
108 6000 524288 65536 7
109 6000 524288 65536 7
110 6000 524288 65536 7
111 6000 524288 65536 7
112 6000 524288 65536 7
113 6000 524288 65536 7
114 6000 524288 65536 7
115 6000 524288 65536 7
116 6000 524288 65536 7
117 6000 524288 65536 7
118 6000 524288 65536 7
119 6000 524288 65536 7
120 6000 524288 65536 7
121 6000 524288 65536 7
Submit
Back to Top