CF1326C Permutation Partitions

给定一个由 $1$ 到 $n$ 的整数构成的排列 $p_1, p_2, \ldots, p_n$，以及一个整数 $k$，其中 $1 \leq k \leq n$。排列的意思是 $1$ 到 $n$ 的每个数在 $p$ 中恰好出现一次。 我们考虑将该排列划分为 $k$ 个不相交的连续区间。形式化地说，一个划分是若干区间的集合 $\{[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\}$，满足： - 对所有 $1 \leq i \leq k$，都有 $1 \leq l_i \leq r_i \leq n$； - 对所有 $1 \leq j \leq n$，恰好存在一个区间 $[l_i, r_i]$，使得 $l_i \leq j \leq r_i$。 如果存在某个区间只属于一个划分而不属于另一个划分，则这两个划分不同。 对于所有可能的划分，将每个划分的值定义为 $\sum\limits_{i=1}^{k} \max\limits_{l_i \leq j \leq r_i} p_j$。请你求出所有划分中可能的最大划分值，以及能达到该最大值的划分个数。由于第二个答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 200\,000$），表示排列的长度和划分的区间数。 第二行包含 $n$ 个不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$），表示给定的排列。

输出两个整数，分别表示所有划分中可能的最大划分值，以及能达到该最大值的划分个数，对 $998\,244\,353$ 取模。

在第一个测试样例中，当 $k = 2$ 时，只有两种有效划分：$\{[1, 1], [2, 3]\}$ 和 $\{[1, 2], [3, 3]\}$。对于每种划分，划分值均为 $2 + 3 = 5$。因此，最大可能的值为 $5$，能达到该值的划分个数为 $2$。 在第三个测试样例中，当 $k = 3$ 时，能达到最大划分值的划分有：$\{[1, 2], [3, 5], [6, 7]\}$，$\{[1, 3], [4, 5], [6, 7]\}$，$\{[1, 4], [5, 5], [6, 7]\}$，$\{[1, 2], [3, 6], [7, 7]\}$，$\{[1, 3], [4, 6], [7, 7]\}$，$\{[1, 4], [5, 6], [7, 7]\}$。对于这些划分，划分值均为 $7 + 5 + 6 = 18$。 而划分 $\{[1, 2], [3, 4], [5, 7]\}$ 的划分值为 $7 + 3 + 6 = 16$，不是最大值，因此不计入答案。 由 ChatGPT 4.1 翻译