Skip to content
Onsite
16 / 26

Permutations With Odd Range Sum

MediumP3Coding

Participants with IDs 1..n are arranged in a row of n places, one per place. Count the arrangements (permutations of 1..n) in which the sum of the IDs at positions l to r, inclusive and 1-based, is odd.

Example 1

Input
n = 3, l = 1, r = 2
Output
4
Why
Of the 6 permutations of 1..3, those with an odd sum in the first two places: 4 of them.

Example 2

Input
n = 3, l = 1, r = 1
Output
4

Example 3

Input
n = 1, l = 1, r = 1
Output
1

Constraints

  • 1 <= n <= 18
  • 1 <= l <= r <= n

Hints

Run checks the 3 visible tests, Submit all 11.