AlternateParity
SRM 848 · 2023-08-03 · by misof
SRM 848 · 2023-08-03 · by misof · Math
Problem Statement
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.
Examples
0)
6 6 Returns: 1
The only fitting sequence is {1, 2, 3, 4, 5, 6}.
1)
5 2 Returns: 6
{1, 2}, {1, 4}, {2, 3}, {2, 5}, {3, 4}, and {4, 5} are the six valid sequences here.
2)
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}.
3)
12 5 Returns: 112
4)
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.
Coding Area
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