Connection Status:
Competition Arena > PermutationCounts

PermutationCounts

SRM 656 · 2015-03-26 · by lg5293

SRM 656 · 2015-03-26 · by lg5293 · Advanced Math
Class Name: PermutationCounts
Return Type: int
Method Name: countPermutations
Arg Types: (int, vector<int>)
Problem Statement

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 1,000,000, inclusive.
  • pos will contain between 0 and min(N-1, 2500) elements, inclusive.
  • Elements of pos will be distinct.
  • Each element of pos will be between 1 and N-1, inclusive.
Examples
0)
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}

1)
13
{12,11,10,9,8,7,6,5,4,3,2,1}
Returns: 1
2)
13
{}
Returns: 1
3)
9
{2,4,5}
Returns: 1421
4)
80
{31,41,59,26,53,58,9,79,32,3,8,46}
Returns: 82650786

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

Coding Area

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

Submitting as anonymous