PROBLEM STATEMENT
You are given an int N and a vector 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:PermutationCounts
Method:countPermutations
Parameters:int, vector
Returns:int
Method signature:int countPermutations(int N, vector pos)
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
5)
875
{295,311,98,345,420,547,646,734,380,325,608,783,141,65,305,437,769,252,44,
872,123,6,50,507,450,426,343,740,69,695,101,607,597,535,342,307,329,837,803,
237,459,444,498,15,712,134,473,14,715,223,787,192,710,750,193,293,242,652,
212,580,545,488,506,533,774,460,285,534,350,210,559,805,686,67,159,541,706,
514,657,801,373,754,310,800,589,736,863,675,254,283,604,27,628,103,81,235,
677,461,609,30,581,75,756,688,262,563,679,21,217,515,836,868,13,728,717,
309,267,767,259,414,332,744,129,859,4,179,632,415,278,812,79,77,784,573,433,
865,407,121,477,567,790,127,593,57,674,114,239,599,552,738}
Returns: 169176190
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)2010, TopCoder, Inc. All rights reserved.