最小値を \(f(x)\) とします。もし、これが求められれば、最大値は

\(\displaystyle \binom{N}{K} - f(\{N+1-x_K, \dots ,N+1-x_1\}) + 1\)

となります。これは、上の写像 \(\{x_1, \dots, x_N\} \mapsto \{N+1-x_K, \dots ,N+1-x_1\}\) が全単射かつ、ちょうど大小関係を反転させることから示されます。

よって以下ではこの \(f(x)\) の求め方を考えます。

---

\(x\) が与えられたとき、求めるべきは以下を満たす数列 \(a\) の個数です。

• \(a_i \le x_i ~ (1 \le i \le N)\)
• \(a_i \lt a_{i+1} ~ (1 \le i \le N - 1)\)

これは、格子上の経路数などと対応付ける事もできますが、\(x_i\) は非常に大きいため、\(1\) から \(x_K\) までの値を一つずつ処理することはできません。

しかし、\((x_{i-1}, x_i]\) の範囲では挙動が大きく変わらないはずですから、これらをまとめて処理してみましょう。

---

DP

次の DP を考えます。

• \(dp[i][j] = x_i\) 以下から \(j\) 頭を選ぶ方法

区間 \((x_i,x_{i+1}]\) に含まれる \(x_{i+1}-x_i\) 頭から \(d\) 頭を選ぶため、以下の遷移を行います。

• \(\displaystyle dp[i+1][j+d] \mathrel{+}= dp[i][j] \binom{x_{i+1}-x_i}{d}\)

ただし \(a_{i+1} \le x_{i+1}\) を満たすためには、 \(x_{i+1}\) 以下から \(i+1\) 頭を選んでいる必要がありますから、遷移は \(j+d \ge i+1\) を満たさなければいけません。

この DP は、状態が \(O(K^2)\) 遷移が \(O(K)\) です。また二項係数についても \(d \le K\) から \(i\) ごとに \(O(K)\) で前計算しておくことができます。よって、全体で \(O(K^3)\) で解く事ができます。

---

実装例

mod = 998244353

n, k = map(int, input().split())
x = list(map(int, input().split()))

inv = [0] * (k + 1)
for i in range(1, k + 1):
    inv[i] = pow(i, mod - 2, mod)

def calc(x):
    dp = [1] + [0] * k
    l = 0
    for i, r in enumerate(x):
        comb = [1] + [0] * k
        for j in range(1, k + 1):
            comb[j] = comb[j-1] * (r - l + 1 - j) % mod
            comb[j] = comb[j] * inv[j] % mod

        ndp = [0] * (k + 1)
        for j in range(i, k + 1):
            for d in range(k - j + 1):
                if j + d > i:
                    ndp[j+d] += dp[j] * comb[d] % mod
                    ndp[j+d] %= mod
        dp = ndp
        l = r
   
    return dp[k]

tmp = 1
for i in range(1, k + 1):
    tmp = tmp * (n + 1 - i) % mod 
    tmp = tmp * inv[i] % mod

mini = calc(x)
maxi = (tmp - calc([n+1-v for v in reversed(x)]) + 1) % mod

print(mini, maxi)

---

bonus : \(O(K^2)\) で解いてみましょう。