### Misa-Misa's blog

By Misa-Misa, 2 months ago, # 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. Comments (12)
 » 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).
 » 2 months ago, # | ← Rev. 2 →   Try to interpret the problem in combinatorical terms. Formally, think of this task instead of what is literally written in the statements. Count the number of arrays $b$ of length $L$, such that... The sum of elements is $N$. Only the first element of $b$ can be even. The rest can be only odd. The part below contain spoilersNow, 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: Define an array $c$, so that $b_i=2c_i+1$. If the parity of $L$ and $N$ do not match, then such an array cannot exist. If the parity of $L$ and $N$ do match, then the number of ways to choose the array $c$ can be simply derived from multiset coefficients. Now do this for both the value $N$ and $N-1$, and the problem is solved.Time complexity: Practically $O(1)$.
 » 2 months ago, # | ← Rev. 2 →   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. Code int ans = 0; for(int i = 1; i+n-1 <= mx; i++){ int rm = mx-(i+n-1); int cnt = rm/2; int cans = choose(n+cnt-1, n-1); ans = add(ans, cans); } 
•  » » I think this can be optimized to only 2 scenarios: 1,2,...nand2,3....n+1
•  » » 2 months ago, # ^ | ← Rev. 2 →   codeif(n <= mx){ int rm = mx-n; int cnt = rm/2; int cans = choose((n+1)+cnt-1, n); ans = add(ans, cans); } if(n+1 <= mx){ int rm = mx-n-1; int cnt = rm/2; int cans = choose((n+1)+cnt-1, n); ans = add(ans, cans); } 
•  » » » Seems, it's A105438.
 » (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). SpoilerFor each k, number of variants with a[L]=a+k is exactly the same for each possible a<=N-k. SpoilerFor 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. SpoilerLet F(k)=0 if k%2=L%2 and F(k)=C(twos(k)+L-1, twos(k)) otherwise. SpoilerAnswer is Sum(F(k)*(N-k)|k=L-1..N-1)It's O(N*logN), I think?