1 2 3 4 ...
Contest: Codeforces Round 696 (Div. 2)
Difficulty rating: 3000
Tags: dp, math, matrices

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}]$$$.

Input format:
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$$$).

Output format:
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$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

Example input:
3
3
1 -1 2

Example output:
3 3

Example input:
3
100
5 -3 6

Example output:
9 7

Editorial:
Solution describes generalized version of algorigthm, corner cases are described later.
It is easy to see that answer doesn't depend on $$$x$$$ given in the input, because we can substract $$$x$$$ from each element of $$$p$$$ and longest incerasing subsequences will remain the same.
Let's look at $$$p$$$ as a function. If $$$p_i = x$$$ and $$$p_j = y$$$, for each $$$z \in [x, y]$$$ there exists $$$k \in [i, j]$$$, such that $$$p_k = z$$$ (Integer version of intermediate value theorem).
Now look at any longest increasing subsequence $$$L$$$. If there are integers $$$x - 1$$$ and $$$x + 1$$$ in it (but there is no $$$x$$$), we can find appearence of $$$x$$$ in $$$p$$$ between them and add it to $$$L$$$, thus making a $$$L$$$ longer. So, such $$$x$$$ shouldn't exist $$$\rightarrow$$$ correct longest increasing sequence contains all integers between $$$a$$$ and $$$b$$$ for some $$$a$$$ and $$$b$$$.
Let's build array $$$peaks$$$ that contains $$$p_1$$$, $$$last(p)$$$ and all $$$p_i$$$ such that $$$p_{i-1} < p_i > p_{i+1}$$$ or $$$p_{i-1} > p_i < p_{i+1}$$$ in order they appear in $$$p$$$. It is easy to see, that $$$|peaks| \leq n + 1$$$.
Suppose, that the end of $$$L$$$ is not a peak. If it lies on increasing interval, than we can take next element into $$$L$$$ and increase $$$|L|$$$. If it lies on decreasing interval, we can use previous element of $$$p$$$ and using previous facts, find $$$L'$$$, $$$|L'| > |L|$$$. We can apply the same observations to the beginning of $$$p$$$.
Thus, any $$$L$$$ begins and ends in peaks. Now, we can find $$$|L|$$$ in $$$\mathcal{O}(n^2)$$$.
Suppose, we fixed that peaks and got $$$p'$$$, such that longest increasing subsequence of $$$p'$$$ begins and ends in different ends of $$$p'$$$ (we will not care about other longest increasing subsequences). Let's look at the slow algorithm for finding the amount of longest increasing subsequences:
• Let $$$ways_i$$$ be number of ways to build a prefix of longest increasing subsequence, that ends in $$$p'_i$$$.
• Set $$$ways_1 = 1$$$.
• For each $$$i$$$ in order $$$[1..|p'|]$$$, $$$ways_i = \sum\limits_{j < i, p'_{j} + 1 = p'_{i}} ways_j$$$. This is correct because $$$p'_{j} + 1 = p'_{i}$$$ means exactly that the length of longest increasing subsequence ends in $$$p'_j$$$ is smaller than the length of longest increasing subsequence ends in $$$p'_i$$$ by $$$1$$$ (because of previous facts).
• The answer is $$$ways_{|p'|}$$$.
The time complexity of this approach is $$$\mathcal{O}(|p'|^2)$$$
Let's change this algorithm a bit by changing order we iterate over $$$i$$$. We will iterate in order of increasing $$$p'_{i}$$$. Since each value appears in $$$p'$$$ $$$\mathcal{O}(n)$$$ times, when calculating values of $$$ways_i$$$ for all $$$i$$$, such that $$$p'_i = x$$$, we will need to check only $$$\mathcal{O}(n)$$$ values of $$$ways_j$$$ for $$$p'_j = x - 1$$$, and we will never use values of $$$ways_j$$$ later, we need only $$$\mathcal{O}(n)$$$ memory and $$$\mathcal{O}(|L| \cdot n^2)$$$ time. We will store this values in array $$$w$$$, where $$$w_{i, j}$$$ is a number of ways to end prefix of longest increasing subsequence in value $$$i$$$ on the $$$j$$$-th increasing/decreasing segment of $$$p'$$$. Clearly, $$$w_{i, j}$$$ is calculated only from $$$w_{i - 1, *}$$$. We can write down transitions between them for each $$$i$$$ and see, that we use the same transition for almost all values of $$$i$$$ between two "consecutive by value" peaks. There are $$$\mathcal{O}(n)$$$ intervals between peaks, and almost all transitions on each of this intervals are the same. We can build matrix $$$G$$$ of size $$$\mathcal{O}(n)$$$ and use matrix exponentiation for doing this transitions fast.
Complexity for each $$$p'$$$ is $$$\mathcal{O}(n^4 \cdot \log|d_{max}|)$$$. We should be careful, because it will take $$$\mathcal{O}(n^6 * \log|d_{max}|)$$$ if we will do it for each $$$p'$$$ we find. We should group $$$p'$$$-s with the same first element into one group and apply the algorithm above for each of the groups. Note, that there can be many groups, but total size (in segments) of all $$$p'$$$-s doesn't exceed $$$n$$$. It gives the total time complexity $$$\mathcal{O}(n^4 \cdot \log|d_{max}|)$$$.
We can further optimize this solution to get time complexity $$$\mathcal{O}(n^3 \cdot \log|d_{max}|)$$$. Obiviously, we can through out all from matrix all rows and collumns with zeroes. After this, we can show that the matrix will be of the following form:
$$$1$$$ $$$1$$$ $$$1$$$ $$$1$$$ $$$1$$$
$$$0$$$ $$$0$$$ $$$1$$$ $$$1$$$ $$$1$$$
$$$0$$$ $$$0$$$ $$$1$$$ $$$1$$$ $$$1$$$
$$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$1$$$
$$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$1$$$
It happends because ones on the main diagonal correspond to increasing subsegments (between two peaks), and zeroes correspond to decreasing subsegments. Obiviously, we cannot move backwards, so all elements below main diagonal are zeroes. And since this matrix corresponds to placing $$$x+1$$$ after $$$x$$$ in longest increasing subsequence, all elements above main diagonal are ones (all subsegments contains both $$$x$$$ and $$$x+1$$$). Matrix exponentiation of this matrix can be done in $$$\mathcal{O}(n^2 \cdot \log|d_{max}|)$$$, because we will care only about distance between $$$i$$$-th and $$$j$$$-th subsegments and parities of $$$i$$$ and $$$j$$$.
There are many tricky cases in this problem, such as:
• Handling zeroes and same sign elements in a row while building $$$peaks$$$.
• If all $$$d_i$$$ are not positive, longest increasing subsequence will have length $$$1$$$ (last element = first element), so it don't have to begin in one of peaks and end in one of peaks.
• Even though all $$$d_i$$$ can be stored in $$$int$$$, first answer can be up to $$$5 \cdot 10^{10} + 1$$$. Also, degree in matrix exponentiation can don't fit in $$$int$$$.
• There can be many groups of $$$p'$$$-s.
• Algorithm without compessing $$$p'$$$-s in groups can work $$$\mathcal{O}(n^6 \cdot \log|d_{max}|)$$$ in the worst case.