Problem Statement
Bear Limak loves algorithms and tolerates data structures. Today he learned about the Cartesian tree. You can find a detailed description of this tree at https://en.wikipedia.org/wiki/Cartesian_tree. Below we give a shorter description that is sufficient to solve this problem.
Let A be a sequence of distinct numbers. Each such sequence defines a unique Cartesian tree. The Cartesian tree is determined by the following rules:
- The Cartesian tree is a rooted binary tree.
- The nodes of the tree correspond to the elements of A.
- An in-order traversal of the tree prints the sequence A.
- The tree is a heap.
A more detailed explanation of the third rule: Consider any node in the tree, and let x be the number in this node. All numbers in the left subtree must appear in A before x, and all numbers in the right subtree must appear in A after x.
A more detailed explanation of the fourth rule: For each node, the number in the node must be strictly smaller than each of the numbers in the children of this node.
Below is a figure that shows the Cartesian tree determined by the sequence A = {9,3,7,1,8,12,10,20,15,18,5}.
We will now define the score of a Cartesian tree. Let T be the Cartesian tree determined by the sequence A. In the tree T there are some nodes that have two children. For each such node, look at the numbers in those two children, find the indices of those two numbers in A, and compute their (positive) difference. The score of the tree T is the sum of all these differences.
For example, in the above tree we have four nodes that have two children each: the nodes with numbers 1, 3, 10, and 15. The children of node 1 are the nodes 3 and 5. In the original sequence A, the values 3 and 5 have (0-based) indices 1 and 10. The difference between these indices is 10 - 1 = 9. For the other three nodes with two children, the differences between their indices are 2, 3, and 2. Hence, the score of this tree is 9 + 2 + 3 + 2 = 16.
You are given the
Definition
- Class:
- BearPermutations
- Method:
- countPermutations
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int countPermutations(int N, int S, int MOD)
- (be sure your method is public)
Notes
- Pay attention to the unusual time limit.
Constraints
- N will be between 1 and 100, inclusive.
- S will be between 0 and 100, inclusive.
- MOD will be between 3 and 10^9, inclusive.
- MOD will be prime.
Examples
3
1
71876209
Returns: 4
For N=3 there are 3! = 6 distinct permutations. Four of these produce Cartesian trees with score 0. The remaining two are the permutations (2,1,3) and (3,1,2). Each of these produces a Cartesian tree with score 2. As we are only interested in trees with score at most 1, there are 4 good permutations.
4
0
1000003
Returns: 8
4
1
483128897
Returns: 8
5
3
907283243
Returns: 82
Two of the 82 permutations that produce valid trees are the permutations (1,3,4,2,5) and (5,4,1,3,2). Each of these permutations produces a tree with score 3.
5
100
101
Returns: 19
All 5! permutations produce valid trees. The answer is (5! modulo 101).
20
30
3
Returns: 2
3
0
13
Returns: 4
3
1
17
Returns: 4
3
2
252832637
Returns: 6
3
3
816584767
Returns: 6
3
4
11
Returns: 6
3
97
460817501
Returns: 6
4
2
558228467
Returns: 18
4
4
7
Returns: 3
4
6
456410347
Returns: 24
5
6
808265659
Returns: 120
7
3
357168899
Returns: 984
10
17
48001103
Returns: 3583926
17
24
935097347
Returns: 240533028
25
11
584350099
Returns: 469172576
31
100
879828539
Returns: 311969414
44
80
17
Returns: 15
50
92
11
Returns: 3
55
67
867907753
Returns: 9880642
61
99
143108129
Returns: 64741942
77
44
993800683
Returns: 27359916
80
3
547940461
Returns: 86015510
92
80
25095233
Returns: 19228743
97
100
947511527
Returns: 933667331
98
0
664803149
Returns: 569820400
98
15
104352683
Returns: 12656403
98
52
378363683
Returns: 228810545
98
80
187548337
Returns: 122174079
98
93
665834033
Returns: 262610354
98
96
154113761
Returns: 13621145
98
100
17
Returns: 1
99
0
949528079
Returns: 42886703
99
54
640487959
Returns: 536006284
99
79
797684731
Returns: 311255385
99
88
754553777
Returns: 733739811
99
97
295772879
Returns: 176247725
99
100
928889657
Returns: 407402555
100
0
751874549
Returns: 732939176
100
15
86538161
Returns: 19068771
100
65
7
Returns: 6
100
72
980576671
Returns: 306897205
100
85
3
Returns: 2
100
97
18292237
Returns: 3039690
100
100
215155649
Returns: 105583167
100
1
363865627
Returns: 270207248
100
33
999727999
Returns: 847762822
100
100
999983
Returns: 538792
100
100
3
Returns: 2
100
100
999999937
Returns: 512182053
3
2
17
Returns: 6
100
100
100000007
Returns: 50612546
99
13
71876209
Returns: 45591215