Problem Statement
In this problem, permutations of order N are arrays of length N that contain each of the values 0 through N-1 exactly once.
Given an array A, its difference array D(A) is the array with one fewer elements, containing the differences between consecutive elements of A.
That is, D(A) = { A[1]-A[0], A[2]-A[1], ... }.
For example, if A = { 10, 20, 27, 25 }, then D(A) = { 10, 7, -2 }.
A permutation is alternating if its difference array alternates between positive and negative integers.
For example, {1, 5, 2, 3, 0, 4} and {3, 0, 2, 1} are both alternating permutations.
You are given the
Count all alternating permutations of order N with the prefix prefix. Return that count modulo 10^9 + 7.
Definition
- Class:
- AlternatingPermutations
- Method:
- count
- Parameters:
- int, int[]
- Returns:
- int
- Method signature:
- int count(int N, int[] prefix)
- (be sure your method is public)
Constraints
- N will be between 1 and 7,000, inclusive.
- prefix will have between 0 and min(50, N) elements, inclusive.
- Each element of prefix will be between 0 and N-1, inclusive.
Examples
10
{4, 4}
Returns: 0
There are no permutations that start {4, 4}.
10
{0, 1, 2}
Returns: 0
There are some permutations that start {0, 1, 2}, but none of them are alternating.
10
{6, 0, 7, 1, 8, 2, 9, 3, 5, 4}
Returns: 1
There is exactly one alternating permutation of order 10 with this prefix: the permutation {6, 0, 7, 1, 8, 2, 9, 3, 5, 4} itself.
10
{6, 0, 7, 1, 8, 2, 9, 3}
Returns: 1
There is still only one alternating permutation with this prefix: {6, 0, 7, 1, 8, 2, 9, 3, 5, 4}.
10
{6, 0, 7, 1, 8, 2, 9}
Returns: 2
Now there are two: {6, 0, 7, 1, 8, 2, 9, 4, 5, 3} is now also a valid alternating permutation.
3
{}
Returns: 4
The empty prefix matches all permutations. The alternating permutations of order 3 are {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, and {2, 0, 1}. Thus, there are 4 of them.
10
{9, 0}
Returns: 1385
10
{2, 7, 4}
Returns: 224
10
{3}
Returns: 11214
10
{}
Returns: 101042
7000
{}
Returns: 778382143
7000
{34}
Returns: 642140559
7000
{14, 4352, 1235, 2555, 3, 12, 7, 154}
Returns: 849984722
1
{}
Returns: 1
1
{0}
Returns: 1
2
{}
Returns: 2
2
{0}
Returns: 1
2
{1}
Returns: 1
2
{0, 1}
Returns: 1
2
{1, 0}
Returns: 1
7000
{14, 4352, 1235, 2555, 3, 14, 7, 154}
Returns: 0
48
{}
Returns: 972463528
58
{32, 24, 16, 21, 25}
Returns: 0
16
{}
Returns: 783024024
36
{34}
Returns: 846637208
4
{3}
Returns: 2
32
{}
Returns: 679780238
69
{4, 30, 45, 47}
Returns: 0
33
{17, 28, 12, 30, 19, 29, 27, 32, 21, 26, 10}
Returns: 33000892
85
{45}
Returns: 15135779
3
{2}
Returns: 1
98
{58}
Returns: 394848840
44
{}
Returns: 721054419
43
{14, 0, 15, 1, 18, 2, 22, 5, 24, 6, 28, 7, 35, 10, 39, 12, 40, 13, 41}
Returns: 955348527
40
{}
Returns: 178869480
99
{}
Returns: 717557091
65
{28, 0, 51, 25, 27}
Returns: 479013406
33
{}
Returns: 557662589
76
{51}
Returns: 889579975
24
{}
Returns: 910697047
37
{12}
Returns: 953137820
53
{3}
Returns: 991100408
75
{0, 39, 1, 41, 2, 43, 4, 44, 8, 45, 9, 47, 11, 48, 14, 50, 16, 52, 17, 55, 18, 56, 19, 57, 21, 58, 24, 61, 29, 62, 30, 65, 32, 67, 33, 68, 34, 69, 35, 70, 36, 71, 37, 72, 38, 74}
Returns: 659646373
41
{3}
Returns: 408840057
33
{28}
Returns: 576471720
70
{32, 1, 33, 2, 36, 3, 40, 5, 41, 6, 42, 7, 44, 8, 46, 9, 48, 12, 49, 13, 51, 14, 55, 15, 56, 16, 57, 17, 58, 18, 59, 19, 60, 20, 62, 22, 63, 24, 65, 26, 67, 28, 68, 30, 69, 31}
Returns: 301846184
94
{68, 54, 19, 25, 34}
Returns: 0
17
{1}
Returns: 295269310
97
{81}
Returns: 560699849
46
{}
Returns: 607612769
95
{59, 81, 15, 63, 19, 67, 64, 69}
Returns: 612892060
56
{5}
Returns: 101593449
60
{}
Returns: 866605286
90
{}
Returns: 246060227
39
{19, 21, 2, 35}
Returns: 914254812
19
{2, 9, 6, 11}
Returns: 446351097
20
{11}
Returns: 547589629
32
{8, 7, 24, 13, 17, 2, 26, 3, 29, 0, 10, 5, 25}
Returns: 596617471
83
{24}
Returns: 657256573
13
{7}
Returns: 3894352
50
{}
Returns: 752426958
42
{}
Returns: 963651725
74
{70}
Returns: 407454034
70
{67}
Returns: 583656305
40
{19, 21, 13, 33, 16, 39, 5, 23, 11}
Returns: 364405972
38
{}
Returns: 520775362
37
{1}
Returns: 562778981
68
{34, 0, 35, 1, 36, 2, 37, 3, 41, 5, 42, 9, 43, 10, 45, 11, 46, 12, 48, 13, 49, 14, 50, 16, 51, 18, 53, 19, 54, 21, 55, 23, 58, 24, 61, 25, 62, 26, 63, 27, 64, 28, 65, 29, 66, 31, 67, 32}
Returns: 126450846
68
{}
Returns: 456293768
42
{32}
Returns: 454959700
70
{5}
Returns: 114698511
18
{10}
Returns: 486507971
6787
{}
Returns: 909002138
6750
{}
Returns: 604834775
6933
{}
Returns: 258669135
6646
{}
Returns: 530974368
6344
{214}
Returns: 117739732
6241
{4558}
Returns: 73294024
6614
{2565, 414, 5224, 2214, 5939, 853, 3302, 707, 1489, 87, 3541, 3084, 3570}
Returns: 336686739
6179
{}
Returns: 762486397
6999
{3278}
Returns: 657814898
6557
{808, 4676, 817, 5091, 764, 6477, 2368, 4176, 1476, 3798, 1554, 5378, 1218, 2096}
Returns: 303636455
6647
{3076, 88, 3175, 107, 3196, 221, 3267, 275, 3838, 378, 3957, 555, 3983, 565, 3998, 718, 4145, 733, 4703, 836, 4794, 883, 4846, 1005, 4975, 1063, 5064, 1071, 5163, 1410, 5216, 1581, 5242, 1998, 5398, 2002, 5941, 2144, 5963, 2571, 6326, 2609, 6468, 2996, 6564}
Returns: 567105818
6206
{63, 3511, 220, 3561, 423, 3608, 490, 3725, 742, 3806, 851, 4009, 980, 4134, 1312, 4319, 1339, 4635, 1494, 4665, 1547, 4794, 1788, 4853, 2442, 4967, 2687, 5121, 2695, 5406, 2819, 5686, 2890, 5700, 3031, 5789, 3090, 5795, 3139, 5889, 3283, 5962, 3437, 6177, 3488}
Returns: 558402329
6649
{}
Returns: 9288435
6385
{218, 3583, 375, 3662, 403, 3769, 630, 3975, 1119, 4245, 1557, 4263, 1760, 4932, 1833, 4974, 1968, 5312, 1985, 5383, 2090, 5458, 2867, 5619, 2879, 5728, 3294, 6091}
Returns: 551376639
6492
{771}
Returns: 461970866
6629
{4733}
Returns: 970275193
6459
{}
Returns: 545340425
6297
{1114}
Returns: 565357126
6696
{5917, 3078, 5558}
Returns: 18838929
6170
{}
Returns: 805745251
6969
{}
Returns: 733948375
6318
{}
Returns: 860639591
6666
{3659, 1794, 243, 1260}
Returns: 0
6658
{6, 4136, 103, 4464, 217, 4712, 1113, 4987, 1734, 5350, 1806, 5363, 2094, 5670, 2111, 5699, 2417, 5772, 2519, 5804, 2866, 5863, 2964, 5945, 3212, 6017, 3252, 6105, 3536, 6181, 3596, 6340, 3666, 6376, 3840, 6402, 4063, 6572, 4131}
Returns: 524098566
6743
{3381, 5480, 2439}
Returns: 152265275
6352
{}
Returns: 618981421
6610
{3872, 145, 4007, 392, 4188, 431, 4316, 455, 4509, 518, 4745, 574, 4755, 782, 4765, 904, 4894, 930, 5112, 997, 5146, 1252, 5165, 1259, 5176, 1793, 5402, 2040, 5515, 2379, 5557, 2383, 5678, 2443, 5881, 2994, 5985, 3224, 6018, 3231, 6057, 3357, 6069, 3368, 6409, 3584, 6589, 3737, 6597, 3855}
Returns: 393337091
6769
{4319}
Returns: 911682730
6228
{}
Returns: 367185017
6828
{}
Returns: 494265339
6011
{1866}
Returns: 971861373
81
{47, 56}
Returns: 262567732
6356
{435, 5396, 4169}
Returns: 847050638
6209
{5894, 5041, 503, 4158}
Returns: 0
96
{29, 37, 65, 76, 78}
Returns: 0
59
{52, 8, 35, 48, 2, 31}
Returns: 0
25
{13, 15, 12, 21, 23, 2, 10, 9, 23, 2, 15, 18, 11, 3}
Returns: 0
17
{3, 3, 0, 12, 0, 15, 2, 12, 16, 5, 2, 0, 12, 7, 7, 13}
Returns: 0
6894
{1572, 6489, 297, 5269, 3216, 2517, 636, 2213, 3751, 3834, 4398, 192, 2010, 1878, 6823, 3425, 129, 4927}
Returns: 0
99
{81, 51, 22, 30, 18, 31, 46, 5, 62, 65, 9, 95, 65, 39, 0, 35, 97, 2, 76, 65, 80, 12}
Returns: 0
49
{29, 31, 17, 17, 18, 26, 42, 47, 40, 18, 47, 22, 45, 0, 45, 28, 11, 15, 21, 4, 8, 21, 37, 27}
Returns: 0
78
{39, 66, 24, 69, 48, 36, 19, 0, 26, 54, 28, 28, 0, 42, 22, 59, 58, 57, 77, 39, 65, 61, 63, 28, 33, 69}
Returns: 0
67
{1, 60, 30, 15, 35, 13, 47, 46, 21, 20, 22, 51, 66, 25, 46, 66, 19, 4, 50, 54, 24, 35, 21, 35, 32, 36, 7, 16}
Returns: 0
6973
{3391, 777, 3825, 5551, 2489, 4996, 238, 4188, 3246, 3263, 1554, 5822, 2579, 3557, 139, 3027, 3458, 532, 3174, 3796, 6921, 5517, 3802, 6058, 2071, 2650, 4328, 6847, 5170, 2031}
Returns: 0
65
{2, 24, 28, 11, 62, 16, 1, 57, 56, 25, 16, 53, 8, 0, 30, 32, 0, 50, 31, 29, 8, 64, 62, 29, 30, 8, 55, 35, 27, 38, 60, 41}
Returns: 0
89
{56, 79, 10, 19, 65, 60, 14, 9, 28, 78, 17, 26, 35, 14, 48, 2, 68, 40, 62, 41, 6, 81, 35, 70, 74, 25, 3, 31, 66, 14, 56, 10, 44, 86}
Returns: 0
6789
{6068, 4834, 6369, 4765, 3392, 4038, 151, 2662, 2630, 6505, 6001, 861, 6541, 4080, 3180, 5665, 6134, 519, 6503, 2473, 3212, 3159, 5055, 5508, 5184, 2503, 4374, 3738, 4731, 6706, 5416, 337, 2454, 6061, 1206, 5289}
Returns: 0
6304
{4761, 6240, 4006, 4962, 5456, 961, 3428, 276, 3538, 3781, 5929, 4929, 6090, 1318, 2442, 4657, 4011, 1281, 4359, 6206, 2893, 2094, 2739, 1410, 4246, 1113, 6103, 299, 0, 632, 2746, 3692, 3330, 4559, 5907, 4205, 3188, 2491}
Returns: 0
1
{ }
Returns: 1
7000
{ }
Returns: 778382143
2
{0 }
Returns: 1
7000
{1, 2 }
Returns: 564842994