#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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

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

14 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