まず、\(B=P\) から始めて \(B=A\) にすることが可能か考えます。\(B\) の同じ要素が複数存在しないことから、\(B\) から整数 \(x\) を削除すると、それ以降 \(x\) 以上の数は削除することが不可能になります。よって、\(A\) に含まれていない要素を大きい順に消す必要があります。

また、\(B\) から \(x\) を削除したときは、\(x\) を含まない極大な区間のうち、\(\mathrm{mex}\) が \(x\) のものを選べば良いです。\(B\) の同じ要素が複数存在しないことから、区間の候補は高々 \(2\) つで、そのうち、\(x\) 未満の要素が全て含まれている方を選べば良いです。

結局以下の条件を全て満たす \(P\) の個数を数え上げれば良いです。

• \(P\) の部分列に \(A\) が存在する
• \(A\) に含まれていない \(0\) 以上 \(N\) 未満の全ての整数 \(x\) について、以下のいずれかが成り立つ
  • \(0\) 以上 \(x\) 未満の整数の index は全て、 \(x\) の index より小さい
  • \(0\) 以上 \(x\) 未満の整数の index は全て、 \(x\) の index より大きい

\(A\) に対して、\(A\) に含まれていない整数を小さい順に条件を満たすように挿入することを考えます。

\(1\) つ目の条件は常に満たします。

\(2\) つ目の条件は整数 \(x\) を挿入するときに、\(x\) 未満の整数のうち一番左にある整数より左に挿入する、もしくは、一番右にある整数より右に挿入するようにすれば良いです。

これを元にして動的計画法を考えます。

\(dp[i][l][r]\) を \(i\) 以下まで挿入が終わった後に、\(i\) 以下の整数のうち一番左にある整数より、左にある整数の数が \(l\) 個であり、\(i\) 以下の整数のうち一番右にある整数より、右にある整数の数が \(r\) 個であるような挿入の方法の場合の数とします。

問題の答えは \(dp[N - 1][0][0]\) となります。

\(A\) に \(0\) が含まれているときは、\(A_{k}=0\) となるような \(k\) を用いて \(dp[0][k - 1][M - k] = 1\) と初期化します。

\(A\) に \(0\) が含まれていないときは、\(i=0, 1, \dots M\) に対して、\(dp[0][i][M - i] = 1\) と初期化します。

\(i=1, 2, \dots N - 1\) の順に \(dp[i]\) を求めます。

\(A\) に \(i\) が含まれているとき

\(A_{k} = i\) であるような \(k\) を用いて、全ての \(l, r\) に対し、以下のように更新すれば良いです。

\[dp[i][\min(l,k - 1)][\min(r,M - k)] += dp[i - 1][l][r]\]

この更新は \(O(M^{2})\) で可能です。

\(A\) に \(i\) が含まれていないとき

以下が成り立ちます。

\[dp[i][l][r] = \sum_{L = l} ^ {M} dp[i - 1][L][r] + \sum_{R=r} ^ {M} dp[i - 1][l][R]\]

これを愚直に行うと、時間計算量が \(O(M ^ {3})\) となりますが、累積和と同様の考えで \(O(M ^ {2})\) で求めることができます。

よって、全体の時間計算量 \(O(N M ^ {2})\) で求めることができます。

下記の実装例では dp table の初期化を上記の通りにしましたが、\(dp[\min(A)]\) を二項係数を用いて直接求めることで、dp table の見るべき範囲が狭くなり、定数倍高速化することが可能です。

定数倍高速化した実装例 :

c++ 34ms

pypy 184 ms

そのままの実装例

c++ 105ms

python

MOD = 998244353

# input etc
N , M = map(int, input().split())
A = list(map(int, input().split()))
B = [-1] * N
for i in range(M):
    B[A[i]] = i

# init
dp = [[0 for j in range(M + 1)] for i in range(M + 1)]
n_dp = [[0 for j in range(M + 1)] for i in range(M + 1)]
# 0 in A
if B[0] != -1:
    dp[B[0]][M - 1 - B[0]] = 1

# 0 not in A
else:
    for i in range(M + 1):
        dp[i][M - i] = 1

# dp
for i in range(1, N):
    
    # i in A
    if B[i] != -1:
        for l in range(M + 1):
            for r in range(M + 1 - l):
                a = min(l, B[i])
                b = min(r, M - 1 - B[i])
                if a != l or b != r:
                    dp[a][b] = (dp[a][b] + dp[l][r]) % MOD
                    dp[l][r] = 0
    
    # i not in A
    else:
        # copy dp
        for l in range(M + 1):
            for r in range(M + 1 - l):
                n_dp[l][r] = dp[l][r]
        #   dp[l][r] = dp[l][r] + dp[l + 1][r] + dp[l + 2][r] + ...
        # n_dp[l][r] = dp[l][r] + dp[l][r + 1] + dp[l][r + 2] + ...
        for l in range(M, -1, -1):
            for r in range(M - l, -1, -1):
                if l != M:
                    dp[l][r] = (dp[l][r] + dp[l + 1][r]) % MOD
                if r != M:
                    n_dp[l][r] = (n_dp[l][r] + n_dp[l][r + 1]) % MOD

        # add
        for l in range(M + 1):
            for r in range(M + 1 - l):
                dp[l][r] = (dp[l][r] + n_dp[l][r]) % MOD


# output
print(dp[0][0])