1 2 3 4 ...

题意翻译

给定一个序列，求其中最长严格上升子序列长度及其个数。 序列按如下方式给出：给定 $n$ 和序列中的第一个数 $x$，接下来 $n$ 个数 $d_i$，若 $d_i>0$，则重复 $d_i$ 次，在序列末尾加上当前序列最后一个数 $+1$ 的值，若 $d_i<0$，重复 $-d_i$ 次，在序列末尾加上当前序列最后一个数 $-1$ 的值。 $1\leq n\leq 50$，$|x|, |d_i| \leq 10^9$。

题目描述

Igor had a sequence $ d_1, d_2, \dots, d_n $ of integers. When Igor entered the classroom there was an integer $ x $ written on the blackboard. Igor generated sequence $ p $ using the following algorithm: 1. initially, $ p = [x] $ ; 2. for each $ 1 \leq i \leq n $ he did the following operation $ |d_i| $ times: - if $ d_i \geq 0 $ , then he looked at the last element of $ p $ (let it be $ y $ ) and appended $ y + 1 $ to the end of $ p $ ; - if $ d_i < 0 $ , then he looked at the last element of $ p $ (let it be $ y $ ) and appended $ y - 1 $ to the end of $ p $ . For example, if $ x = 3 $ , and $ d = [1, -1, 2] $ , $ p $ will be equal $ [3, 4, 3, 4, 5] $ . Igor decided to calculate the length of the longest increasing subsequence of $ p $ and the number of them. A sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) elements. A sequence $ a $ is an increasing sequence if each element of $ a $ (except the first one) is strictly greater than the previous element. For $ p = [3, 4, 3, 4, 5] $ , the length of longest increasing subsequence is $ 3 $ and there are $ 3 $ of them: $ [\underline{3}, \underline{4}, 3, 4, \underline{5}] $ , $ [\underline{3}, 4, 3, \underline{4}, \underline{5}] $ , $ [3, 4, \underline{3}, \underline{4}, \underline{5}] $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \leq n \leq 50 $ ) — the length of the sequence $ d $ . The second line contains a single integer $ x $ ( $ -10^9 \leq x \leq 10^9 $ ) — the integer on the blackboard. The third line contains $ n $ integers $ d_1, d_2, \ldots, d_n $ ( $ -10^9 \leq d_i \leq 10^9 $ ).

输出格式

Print two integers: - the first integer should be equal to the length of the longest increasing subsequence of $ p $ ; - the second should be equal to the number of them modulo $ 998244353 $ . You should print only the second number modulo $ 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

说明

The first test case was explained in the statement. In the second test case $ p = [100, 101, 102, 103, 104, 105, 104, 103, 102, 103, 104, 105, 106, 107, 108] $ . In the third test case $ p = [1, 2, \ldots, 2000000000] $ .

题意翻译

给定一个序列，求其中最长严格上升子序列长度及其个数。 序列按如下方式给出：给定 $n$ 和序列中的第一个数 $x$，接下来 $n$ 个数 $d_i$，若 $d_i>0$，则重复 $d_i$ 次，在序列末尾加上当前序列最后一个数 $+1$ 的值，若 $d_i<0$，重复 $-d_i$ 次，在序列末尾加上当前序列最后一个数 $-1$ 的值。 $1\leq n\leq 50$，$|x|, |d_i| \leq 10^9$。