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 int N and a int[] prefix.
Count all alternating permutations of order N with the prefix prefix. Return that count modulo 10^9 + 7.
Definition
- Class:
- AlternatingPermutations
- Method:
- count
- Parameters:
- int, int[]
- Returns:
- int
- Method signature:
- int count(int N, int[] prefix)
- (be sure your method is public)
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.
Examples
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.10
{9, 0}Returns: 1385