P - Priority Queue 3
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
N 個の +
と M 個の -
からなる長さ N+M の文字列 S、および M 個の整数からなる集合 A=\lbrace A_1,A_2,\dots,A_M\rbrace が与えられます。
集合 X=\lbrace \rbrace,Y=\lbrace \rbrace を用意し、i=1,2,\dots,N+M の順に以下を行うことを考えます。
- S の i 文字目が
+
のとき、1 から N までの整数のうち、X,Y のいずれにも含まれない整数を 1 つ選び、X に追加する。 - S の i 文字目が
-
のとき、X に含まれる整数の最小値 m を X から削除し、m を Y に追加する。制約から、操作の直前に X は空でないことが保証される。
一連の操作で X に追加する整数の順番は N! 通り考えられますが、そのうち一連の操作を終えた後に Y=A となっているような順番の数を 998244353 で割った余りを求めてください。
制約
- 入力される数値は全て整数
- 1 \leq M \leq N \leq 300
- S は N 個の
+
と M 個の-
からなる長さ N+M の文字列 - i=1,2,\dots,N+M に対し、S の i 文字目までに登場する
-
の数は i 文字目までに登場する+
の数を超えない - 1 \leq A_1 < A_2 < \dots < A_M \leq N
入力
入力は以下の形式で標準入力から与えられる。
N M S A_1 A_2 \dots A_M
出力
答えを 1 行に出力せよ。
入力例 1
4 2 ++-++- 1 3
出力例 1
4
条件を満たす一連の操作の例として以下のようなものが考えられます。
- i=1 のとき、X に 3 を追加する。X=\lbrace 3\rbrace,Y=\lbrace \rbrace となる。
- i=2 のとき、X に 4 を追加する。X=\lbrace 3,4\rbrace,Y=\lbrace \rbrace となる。
- i=3 のとき、X に含まれる整数の最小値 3 を X から削除して Y に追加する。X=\lbrace 4\rbrace,Y=\lbrace 3\rbrace となる。
- i=4 のとき、X に 2 を追加する。X=\lbrace 2,4\rbrace,Y=\lbrace 3\rbrace となる。
- i=5 のとき、X に 1 を追加する。X=\lbrace 1,2,4\rbrace,Y=\lbrace 3\rbrace となる。
- i=6 のとき、X に含まれる整数の最小値 1 を X から削除して Y に追加する。X=\lbrace 2,4\rbrace,Y=\lbrace 1,3\rbrace となる。
入力例 2
6 4 ++-++---++ 2 3 4 6
出力例 2
48
S の末尾は -
とは限りません。
入力例 3
20 10 ++++-++++++--+--+-+++++--+-++- 1 2 3 4 5 6 7 9 12 13
出力例 3
179396825