IncreasingSequencesEasy
SRM 728 · 2018-01-24 · by tourist
SRM 728 · 2018-01-24 · by tourist · Dynamic Programming
Problem Statement
Problem Statement
You are given two
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.
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
0)
{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}.
1)
{10, 20}
{20, 30}
Returns: 120
2)
{20, 10}
{30, 20}
Returns: 0
3)
{4, 46, 46, 35, 20, 77, 20}
{41, 65, 84, 90, 49, 86, 88}
Returns: 2470
4)
{1, 1, 1}
{10000, 10000, 10000}
Returns: 908107402
Don't forget about the modulo.
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class IncreasingSequencesEasy with a public method int count(vector<int> L, vector<int> R) · 65 test cases · 2 s / 256 MB per case