#	User	Rating
1	tourist	3985
2	jiangly	3741
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3489
7	Radewoosh	3483
8	Kevin114514	3442
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	atcoder_official	162
2	maomao90	162
2	Um_nik	162
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	nor	150

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 (11)

Show archived | Write comment?

Misa-Misa

15 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$$$?

15 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);  
}

kellendros95

(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).

Spoiler

Misa-Misa's blog

Problem

Constraints

What I have been able to do upto now

Then i further observed that