← 返回题目列表

Codeforces · 1326/C

C. 排列分区

中文机器翻译题面 查看原题

给你一个从 $$$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 l_i \leq r_i \leq n$$$ 对于所有 $$$1 \leq i \leq k$$$;
- 对于所有$$$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}}$$$,将所有可能的排列分区划分为 $$$k$$$ 不相交段。查找所有此类分区的最大可能分区值,以及具有该值的分区数。由于第二个值可能非常大,因此您应该找到除以 $$$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$$$) - 给定的排列。

输出

打印两个整数 - $$$k$$$ 不相交段的排列的所有分区的最大可能分区值,以及分区值等于最大可能值的此类分区的数量,以 $$$998\,244\,353$$$ 为模。

请注意,您只能找到对 $$$998\,244\,353$$$ 取模的第二个值。

示例

输入 #1

3 2
2 1 3

输出 #1

5 2

输入 #2

5 5
2 1 5 3 4

输出 #2

15 1

输入 #3

7 3
2 7 3 1 5 4 6

输出 #3

18 6

注意

在第一个测试中,对于 $$$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$$$。这不是最大可能值,因此我们不计算它。