AlternateParity
SRM 848 · 2023-08-03 · by misof
Problem Statement
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 10^9 + 7.
Constraints
- N will be between 1 and 100,000, inclusive.
- L will be between 1 and N, inclusive.
Statement by TopCoder, Inc. — view the original on the archive.
6 6 Returns: 1
The only fitting sequence is {1, 2, 3, 4, 5, 6}.
5 2 Returns: 6
{1, 2}, {1, 4}, {2, 3}, {2, 5}, {3, 4}, and {4, 5} are the six valid sequences here.
12 4 Returns: 105
A few of these 105 sequences: {1, 2, 5, 10}, {2, 5, 8, 11}, {3, 6, 7, 8}, and {5, 8, 9, 12}.
12 5 Returns: 112
13 4 Returns: 140
Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlternateParity with a public method int count(int N, int L) · 24 test cases · 2 s / 256 MB per case