← 返回题目列表

Codeforces · 1474/F

F. 一二三四……

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

Igor 有一个整数序列 $$$d_1, d_2, \dots, d_n$$$。当伊戈尔走进教室时,黑板上写着一个整数$$$x$$$。

Igor 使用以下算法生成序列 $$$p$$$:

1. 最初,$$$p = [x]$$$;
2. 对于每个 $$$1 \leq i \leq n$$$,他执行以下操作 $$$|d_i|$$$ 次:如果 $$$d_i \geq 0$$$,则他查看 $$$p$$$ 的最后一个元素(假设为 $$$y$$$)并将 $$$y + 1$$$ 附加到 $$$p$$$ 的末尾; 如果 $$$d_i < 0$$$,那么他查看 $$$p$$$ 的最后一个元素(假设为 $$$y$$$)并将 $$$y - 1$$$ 附加到 $$$p$$$ 的末尾。

例如,如果 $$$x = 3$$$,且 $$$d = [1, -1, 2]$$$,则 $$$p$$$ 将等于 $$$[3, 4, 3, 4, 5]$$$。

Igor 决定计算 $$$p$$$ 的最长递增子序列的长度及其数量。

如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是序列 $$$b$$$ 的子序列。

如果 $$$a$$$ 的每个元素(第一个元素除外)严格大于前一个元素,则序列 $$$a$$$ 是递增序​​列。

对于 $$$p = [3, 4, 3, 4, 5]$$$,最长递增子序列的长度为 $$$3$$$,其中有 $$$3$$$: $$$[\underline{3}, \underline{4}, 3, 4, \underline{5}]$$$, $$$[\underline{3}, 4, 3、\下划线{4}、\下划线{5}]$$$、$$$[3、4、\下划线{3}、\下划线{4}、\下划线{5}]$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) — 序列 $$$d$$$ 的长度。

第二行包含一个整数 $$$x$$$ ($$$-10^9 \leq x \leq 10^9$$$) — 黑板上的整数。

第三行包含 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$ ($$$-10^9 \leq d_i \leq 10^9$$$)。

输出

打印两个整数:

- 第一个整数应等于 $$$p$$$ 的最长递增子序列的长度;
- 第二个应该等于它们的数量模$$$998244353$$$。

您应该只打印第二个数字模$$$998244353$$$。

示例

输入 #1

3
3
1 -1 2

输出 #1

3 3

输入 #2

3
100
5 -3 6

输出 #2

9 7

输入 #3

3
1
999999999 0 1000000000

输出 #3

2000000000 1

输入#4

5
34
1337 -146 42 -69 228

输出#4

1393 3876

注意

第一个测试用例在声明中进行了解释。

在第二个测试用例中 $$$p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108]$$$。

在第三个测试用例中 $$$p = [1, 2, \ldots, 2000000000]$$$。