PermutationCountsDiv2

SRM 656 · 2015-03-26 · by lg5293

SRM 656 · 2015-03-26 · by lg5293 · Advanced Math

Show categories

Class Name: PermutationCountsDiv2

Return Type: int

Method Name: countPermutations

Arg Types: (int, vector<int>)

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.

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.

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

13
{}
Returns: 1

9
{2,4,5}
Returns: 1421

80
{31,41,59,26,53,58,9,79,32,3,8,46}
Returns: 82650786

Submissions are judged against all 47 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PermutationCountsDiv2 with a public method int countPermutations(int N, vector<int> pos) · 47 test cases · 2 s / 256 MB per case