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)

Write comment?

Misa-Misa

8 months ago, # |

Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).

→ Reply

nifeshe

+22

What does $$$N$$$ represent in the problem? The upper bound on $$$a_L$$$?

8 months ago, # ^ |

yup

chromate00

← Rev. 2 →

+16

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 spoilers

AmmarDab3an

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,...n

and

2,3....n+1

code

if(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);  
}