AlternatingPermutations
SRM 840 · 2022-10-24 · by misof
Problem Statement
In this problem, permutations of order N are arrays of length N that contain each of the values 0 through N-1 exactly once.
Given an array A, its difference array D(A) is the array with one fewer elements, containing the differences between consecutive elements of A.
That is, D(A) = { A[1]-A[0], A[2]-A[1], ... }.
For example, if A = { 10, 20, 27, 25 }, then D(A) = { 10, 7, -2 }.
A permutation is alternating if its difference array alternates between positive and negative integers.
For example, {1, 5, 2, 3, 0, 4} and {3, 0, 2, 1} are both alternating permutations.
You are given the
Count all alternating permutations of order N with the prefix prefix. Return that count modulo 10^9 + 7.
Constraints
- N will be between 1 and 7,000, inclusive.
- prefix will have between 0 and min(50, N) elements, inclusive.
- Each element of prefix will be between 0 and N-1, inclusive.
10
{4, 4}
Returns: 0
There are no permutations that start {4, 4}.
10
{0, 1, 2}
Returns: 0
There are some permutations that start {0, 1, 2}, but none of them are alternating.
10
{6, 0, 7, 1, 8, 2, 9, 3, 5, 4}
Returns: 1
There is exactly one alternating permutation of order 10 with this prefix: the permutation {6, 0, 7, 1, 8, 2, 9, 3, 5, 4} itself.
10
{6, 0, 7, 1, 8, 2, 9, 3}
Returns: 1
There is still only one alternating permutation with this prefix: {6, 0, 7, 1, 8, 2, 9, 3, 5, 4}.
10
{6, 0, 7, 1, 8, 2, 9}
Returns: 2
Now there are two: {6, 0, 7, 1, 8, 2, 9, 4, 5, 3} is now also a valid alternating permutation.
3
{}
Returns: 4
The empty prefix matches all permutations. The alternating permutations of order 3 are {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, and {2, 0, 1}. Thus, there are 4 of them.
Submissions are judged against all 124 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlternatingPermutations with a public method int count(int N, vector<int> prefix) · 124 test cases · 2 s / 256 MB per case