122 . 孤獨搖滾

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

littlecube

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (6/6)

Tags

ioicamp ioicamp-2023

Description

有一個圓，圓周上有 $N$ 個等距分布的點，其中每個點是紅色或藍色。這 $N$ 個點分出的 $N$ 段弧每個被塗成粉色或黃色。現在，你可以在這 $N$ 個點之間連出一些弦，必須滿足弦的端點要是同色的點，且連出來的弦之間不能共點（包含端點也不能共用）。是否存在一種連出弦的方法，使得用這些弦把圓切開的話，每塊的圓周部分都只有一種顏色的圓弧（不同時有粉色跟黃色）？

然而現在這個問題對你來說實在過於簡單，於是你想要更進一步知道以下問題的答案：

給定一個長度 $2N$ 的字串，奇數位置的字元可能是 P, Y, ? 中的任一個，偶數位置的字元可能是 R, B, ? 中的任一個，其中 P, Y 分別代表粉色跟黃色的弧，R, B 分別代表紅色跟藍色的點。請問有幾種將每個問號都填成該位置奇偶性可以填的顏色的方法，使得產生的配置在前述問題的答案是肯定的？請輸出答案對 $998244353$ 取模後的餘數。

舉例來說，在 $N = 2$ 的所有可能字串中，一共有以下 $12$ 種字串的答案是肯定的：

  • YBYB
  • YBYR
  • YRYB
  • YRYR
  • PBPB
  • PBPR
  • PRPB
  • PRPR
  • YBPB
  • YRPR
  • PBYB
  • PRYR

Input Format

輸入第一行只有一個正整數 $N$，代表圓周上的點數。

輸入第二行包含一個長度為 $2N$ 的字串，格式如題目中所述。

  • $2 \leq N \leq 50000$

Output Format

請輸出一個整數代表一共有幾種方法填入將字元 ? 使得答案是肯定的。請將答案模 $998244353$ 之後輸出。

Sample Input 1

2
????

Sample Output 1

12

Sample Input 2

3
??YR?B

Sample Output 2

4

Sample Input 3

5
YBYRPBYRYB

Sample Output 3

0

Hints

Problem Source

IOICamp 2023 Day4 pE

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~14 至多只有十個位置是 ? 20
3 0~2, 15~24 $N \leq 5000$ 30
4 0~34 無特別限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 7000 524288 65536 1 2 3 4
1 7000 524288 65536 1 2 3 4
2 7000 524288 65536 1 2 3 4
3 7000 524288 65536 2 4
4 7000 524288 65536 2 4
5 7000 524288 65536 2 4
6 7000 524288 65536 2 4
7 7000 524288 65536 2 4
8 7000 524288 65536 2 4
9 7000 524288 65536 2 4
10 7000 524288 65536 2 4
11 7000 524288 65536 2 4
12 7000 524288 65536 2 4
13 7000 524288 65536 2 4
14 7000 524288 65536 2 4
15 7000 524288 65536 3 4
16 7000 524288 65536 3 4
17 7000 524288 65536 3 4
18 7000 524288 65536 3 4
19 7000 524288 65536 3 4
20 7000 524288 65536 3 4
21 7000 524288 65536 3 4
22 7000 524288 65536 3 4
23 7000 524288 65536 3 4
24 7000 524288 65536 3 4
25 7000 524288 65536 4
26 7000 524288 65536 4
27 7000 524288 65536 4
28 7000 524288 65536 4
29 7000 524288 65536 4
30 7000 524288 65536 4
31 7000 524288 65536 4
32 7000 524288 65536 4
33 7000 524288 65536 4
34 7000 524288 65536 4
Submit
Back to Top