Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 枚のカードが左から右に並んでいます。 各カードに 1 以上 K 以下の整数を書き込みます。はじめ、どのカードにも整数は書かれていません。
1 から K の番号がついた K 個の制約が与えられます。
制約 i は文字 c_i と整数 k_i からなります。
c_i が L
ならば、i が書かれたカードのうち最も 左 にあるものは N 枚のカードのうち左から k_i 番目である必要があります。c_i が R
ならば、i が書かれたカードのうち最も 右 にあるものは N 枚のカードのうち左から k_i 番目である必要があります。
1 以上 K 以下の各整数 i について、i が書かれたカードが少なくとも 1 つ存在する必要があることに注意してください。
上記の K 個の制約をすべて満たすようなカードへの整数の書き込み方の個数を 998244353 で割ったあまりを求めてください。
制約
- 1 \leq N,K \leq 1000
- c_i は
L
,R
のいずれか - 1 \leq k_i \leq N
- i \neq j ならば k_i \neq k_j
入力
入力は以下の形式で標準入力から与えられる。
N K c_1 k_1 \vdots c_K k_K
出力
問題文中の K 個の制約をすべて満たすようなカードへの整数の書き込み方の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
3 2 L 1 R 2
出力例 1
1
- 左から 1 番目のカードに 1 を、2 番目のカードに 2 を、3 番目のカードに 1 を書き込むのが 2 つの制約を満たすような唯一の書き込み方です。
入力例 2
30 10 R 6 R 8 R 7 R 25 L 26 L 13 R 14 L 11 L 23 R 30
出力例 2
343921442
- 998244353 で割ったあまりを求めるのを忘れずに。
Score : 300 points
Problem Statement
We have N cards arranged in a row from left to right. We will write an integer between 1 and K (inclusive) on each of these cards, which are initially blank.
Given are K restrictions numbered 1 through K.
Restriction i is composed of a character c_i and an integer k_i.
If c_i is L
, the k_i-th card from the left in the row must be the leftmost card on which we write i.
If c_i is R
, the k_i-th card from the left in the row must be the rightmost card on which we write i.
Note that for each integer i from 1 through K, there must be at least one card on which we write i.
Find the number of ways to write integers on the cards under the K restrictions, modulo 998244353.
Constraints
- 1 \leq N,K \leq 1000
- c_i is
L
orR
. - 1 \leq k_i \leq N
- k_i \neq k_j if i \neq j.
Input
Input is given from Standard Input in the following format:
N K c_1 k_1 \vdots c_K k_K
Output
Find the number of ways to write integers on the cards under the K restrictions in the Problem Statement, modulo 998244353.
Sample Input 1
3 2 L 1 R 2
Sample Output 1
1
- The only way to meet the two restrictions is to write 1, 2, 1 from left to right on the three cards.
Sample Input 2
30 10 R 6 R 8 R 7 R 25 L 26 L 13 R 14 L 11 L 23 R 30
Sample Output 2
343921442
- Be sure to find the count modulo 998244353.