You are given positive integers
L. Count all sequences of positive integers with the following properties:
- The sequence is strictly increasing.
- The length of the sequence is
- No two consecutive elements share the same parity.
Return the number of these sequences, modulo
1e9 + 7.
N <= 1e5 and
L <= N.
elements in sequence can be from
What I have been able to do upto now
I broke it into two parts.
- Part 1 : o e o e o e ...
- Part 2 : e o e o e o ...
I have thought of
Then Lets solve for
o e o e .., second part will be similar.
dp[i][j] : Number of ways to fill upto index
i such that number at index
i is odd then
j must be odd.
dp[i][j] = dp[i-2][j-2] * 1 + dp[i-2][j-4] * 2 + dp[i-2][j-6] * 3 ... -- eq1
Then i further observed that
dp[i][j-2] = dp[i-2][j-4] * 1 + dp[i-2][j-6] * 2 + dp[i-1][j-8] * 3 ... --eq2
eq1 - eq2 gives me,
dp[i][j] = dp[i][j-2] + dp[i-2][j-2] + dp[i-2][j-4] + dp[i-2][j-6] + dp[i-2][j-8] ...
this can now be done in
O(N*N), but will surely give TLE in above constraints.
So how to proceed further?
Are there any optimization / tricks in this dp.
Or I should think something else which is not dp.
Don't wanna know the solution, just tell if there is some general concept/trick that i need to know, or i just need to think more on it.