PermutationCountsDiv2 | Topcoder Archive

Problem Statement

You are given an int N and a int[] pos. We are interested in some permutations of the set {1,2,...,N}. A permutation p is called good if the following condition is satisfied: for each valid k, we have p(k) < p(k+1) if and only if k is an element of pos.

Return the number of good permutations, modulo 1,000,000,007.

Definition

Class:: PermutationCountsDiv2
Method:: countPermutations
Parameters:: int, int[]
Returns:: int
Method signature:: int countPermutations(int N, int[] pos)
(be sure your method is public)

Constraints

N will be between 1 and 200, inclusive.
pos will contain between 1 and N-1 elements, inclusive.
Elements of pos will be distinct.
Each element of pos will be between 1 and N-1, inclusive.

Examples

```
5
```
```
{3}
```
```
Returns: 9
```
Given that pos = {3}, we are looking for permutations where p(1) > p(2), p(2) > p(3), p(3) < p(4), and p(4) > p(5). Thus, the good permutations are the following ones: {3,2,1,5,4} {4,2,1,5,3} {4,3,1,5,2} {4,3,2,5,1} {5,2,1,4,3} {5,3,1,4,2} {5,3,2,4,1} {5,4,1,3,2} {5,4,2,3,1} Here, the notation {3,2,1,5,4} represents the permutation p for which p(1)=3, p(2)=2, p(3)=1, p(4)=5, and p(5)=4.

{12,11,10,9,8,7,6,5,4,3,2,1}

Returns: 1

```
13
```
```
{}
```
```
Returns: 1
```
```
9
```
```
{2,4,5}
```
```
Returns: 1421
```

{31,41,59,26,53,58,9,79,32,3,8,46}

Returns: 82650786

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.