IncreasingSequencesEasy | Topcoder Archive

Problem Statement

You are given two int[]s L and R, each of length n.

Find the number of strictly increasing sequences of integers A[0] < A[1] < ... < A[n-1] such that L[i] ≤ A[i] ≤ R[i] for every i. Return this number modulo 998244353.

Definition

Class:: IncreasingSequencesEasy
Method:: count
Parameters:: int[], int[]
Returns:: int
Method signature:: int count(int[] L, int[] R)
(be sure your method is public)

Notes

The number 998244353 is a prime number.

Constraints

n will be between 1 and 300, inclusive.
L will contain exactly n elements.
R will contain exactly n elements.
L[i] will be between 1 and 104, inclusive.
R[i] will be between L[i] and 104, inclusive.

Examples

```
{1, 3, 1, 4}
```
```
{6, 5, 4, 6}
```
```
Returns: 4
```
There are 4 strictly increasing sequences satisfying the conditions: {1, 3, 4, 5}, {1, 3, 4, 6}, {2, 3, 4, 5} and {2, 3, 4, 6}.
```
{10, 20}
```
```
{20, 30}
```
```
Returns: 120
```
```
{20, 10}
```
```
{30, 20}
```
```
Returns: 0
```

{4, 46, 46, 35, 20, 77, 20}

{41, 65, 84, 90, 49, 86, 88}

Returns: 2470

{1, 1, 1}

{10000, 10000, 10000}

Returns: 908107402

Don't forget about the modulo.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.