重要な事実として、\(i \neq j\) なる \(i,j\) について左から \(i\) 番目のカードに書き込む整数が \(j\) 番目のカードに影響を与えることはありません。 それぞれのカードについて書き込むことができる整数の種類数を求めましょう。

ある整数 \(x\) を左から \(i\) 番目に書き込むことができるのは以下の条件 \(1\) と、条件 \(2,3\) のどちらかを満たしている場合に限られます。

1. \(x \neq y\) なる整数 \(y\) であって \(k_y =i\) なる \(y\) が存在しない
2. \(c_x\) が L であり、\(k_x \leq i\)
3. \(c_x\) が R であり、\(i \leq k_x\)

上記のアルゴリズムは時間計算量 \(O(NK)\) で動作し、十分高速です。

実装例(C++)

#include <iostream>
#include <vector>
using ll = long long;
using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> a(N, 0);
    vector<int> b(N, 0);
    for (int i = 0; i < K; i++)
    {
        char c;
        int k;
        cin >> c >> k;
        k--;
        b[k] = 1;
        for (int j = 0; j < N; j++)
        {
            if (c == 'L' && k <= j)
                a[j]++;
            if (c == 'R' && j <= k)
                a[j]++;
        }
    }
    const ll MOD = 998244353;
    ll ans = 1;
    for (int i = 0; i < N; i++)
        if (!b[i])
            ans = ans * a[i] % MOD;

    cout << ans << endl;
    return 0;
}