Problem
You are given positive integers N and L. Count all sequences of positive integers with the following properties:
- The sequence is strictly increasing.
- The length of the sequence is L.
- No two consecutive elements share the same parity.
Return the number of these sequences, modulo 1e9 + 7.
Constraints
N <= 1e5 and L <= N.
elements in sequence can be from 1 to N.
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 dp.
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 j. If 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
This is O(N*N*N) Solution.
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
Then 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.
Thanks.
Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).
Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).
Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).
What does $$$N$$$ represent in the problem? The upper bound on $$$a_L$$$?
yup
Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).
Try to interpret the problem in combinatorical terms. Formally, think of this task instead of what is literally written in the statements.
Now, we can see that the arrays $$$b$$$ correspond one-to-one to arrays $$$a$$$ defined in the statements, because the prefix sum of $$$b$$$ is $$$a$$$, and the adjacent difference of $$$a$$$ is $$$b$$$. Then, the last constraint can also be removed, because the answer with an even $$$b_1$$$ will be equal to the answer with sum $$$N-1$$$ and an odd $$$b_1$$$. So, we can now just care about odd numbers now. Let us solve the task as follows:
Now do this for both the value $$$N$$$ and $$$N-1$$$, and the problem is solved.
Time complexity: Practically $$$O(1)$$$.
Any sequence that fulfills the said conditions can be constructed like this:
Start with a continuous segment of the numbers 1,2,...N, like [i, i+L-1].
Now consider each suffix of this sequence, you can add any even amount to it as long as the value of the largest element (the last element) doesn't exceed N.
To make it easier, try thinking of the remaining value (N — (i+L-1)) as AddSuffix(i, +2) operations up to (N-(i+L-1))/2 times. Now you only have to think about how to distribute some of those operations on the suffixes of the sequence.
In order to consider not using all those operations, you can add an additional element at the end of the sequence, which will not be included in the final sequence.
Time complexity O(N).
in my code, I use n=L and mx=N.
I think this can be optimized to only 2 scenarios:
1,2,...n
and
2,3....n+1
(I can be wrong)
Between each two consequtive elemets we need to add 1 exactly one time and add 2 some number of times (maybe 0).
For each k, number of variants with a[L]=a[1]+k is exactly the same for each possible a[1]<=N-k.
For fixed k with the same parity as L-1 we know how many times total we need to add 2, the quesstion is only when we add them. It's twos(k)=(k-L+1)/2.
Let F(k)=0 if k%2=L%2 and F(k)=C(twos(k)+L-1, twos(k)) otherwise.
Answer is Sum(F(k)*(N-k)|k=L-1..N-1)
It's O(N*logN), I think?