Problem Statement
Consider the permutation a=(a[0], a[1], ..., a[n-1]) of integers from 0 to n-1, inclusive. Its inverse permutation is b=(b[0], b[1], ..., b[n-1]), where b[a[i]]=i. For example, the inverse permutation of (2, 0, 3, 1, 4) is (1, 3, 0, 2, 4).
We say that permutation a is k-slope if its inversion permutation b has exactly k positions i, such that b[i] > b[i+1]. For example, permutation (2, 0, 3, 1, 4) is 1-slope because its inverse, (1, 3, 0, 2, 4), has exactly one such position (at i=1: 3 > 0).
You are given
Definition
- Class:
- KSlopePermutation
- Method:
- getCount
- Parameters:
- int, int, int
- Returns:
- long
- Method signature:
- long getCount(int n, int k, int f)
- (be sure your method is public)
Constraints
- n will be between 1 and 20, inclusive.
- k will be between 0 and n-1, inclusive.
- f will be between 0 and n-1, inclusive.
Examples
4
1
0
Returns: 4
The permutations are (0, 1, 3, 2), (0, 2, 1, 3), (0, 2, 3, 1) and (0, 3, 1, 2).
2
1
0
Returns: 0
For n = 2, the only permutation that starts with 0 is (0, 1) which is 0-slope.
3
0
1
Returns: 0
The only 0-slope permutation is (0, 1, 2).
7
3
2
Returns: 330
1
0
0
Returns: 1
2
0
0
Returns: 1
2
0
1
Returns: 0
2
1
0
Returns: 0
2
1
1
Returns: 1
3
0
0
Returns: 1
3
0
1
Returns: 0
3
0
2
Returns: 0
3
1
0
Returns: 1
3
1
1
Returns: 2
3
1
2
Returns: 1
3
2
0
Returns: 0
3
2
1
Returns: 0
3
2
2
Returns: 1
4
0
0
Returns: 1
4
0
1
Returns: 0
4
0
2
Returns: 0
4
0
3
Returns: 0
4
1
0
Returns: 4
4
1
1
Returns: 3
4
1
2
Returns: 3
4
1
3
Returns: 1
4
2
0
Returns: 1
4
2
1
Returns: 3
4
2
2
Returns: 3
4
2
3
Returns: 4
4
3
0
Returns: 0
4
3
1
Returns: 0
4
3
2
Returns: 0
4
3
3
Returns: 1
5
0
0
Returns: 1
5
0
1
Returns: 0
5
0
2
Returns: 0
5
0
3
Returns: 0
5
0
4
Returns: 0
5
1
0
Returns: 11
5
1
1
Returns: 4
5
1
2
Returns: 6
5
1
3
Returns: 4
5
1
4
Returns: 1
5
2
0
Returns: 11
5
2
1
Returns: 16
5
2
2
Returns: 12
5
2
3
Returns: 16
5
2
4
Returns: 11
5
3
0
Returns: 1
5
3
1
Returns: 4
5
3
2
Returns: 6
5
3
3
Returns: 4
5
3
4
Returns: 11
5
4
0
Returns: 0
5
4
1
Returns: 0
5
4
2
Returns: 0
5
4
3
Returns: 0
5
4
4
Returns: 1
6
0
0
Returns: 1
6
0
1
Returns: 0
6
0
2
Returns: 0
6
0
3
Returns: 0
6
0
4
Returns: 0
6
0
5
Returns: 0
6
1
0
Returns: 26
6
1
1
Returns: 5
6
1
2
Returns: 10
6
1
3
Returns: 10
6
1
4
Returns: 5
6
1
5
Returns: 1
6
2
0
Returns: 66
6
2
1
Returns: 55
6
2
2
Returns: 50
6
2
3
Returns: 50
6
2
4
Returns: 55
6
2
5
Returns: 26
6
3
0
Returns: 26
6
3
1
Returns: 55
6
3
2
Returns: 50
6
3
3
Returns: 50
6
3
4
Returns: 55
6
3
5
Returns: 66
6
4
0
Returns: 1
6
4
1
Returns: 5
6
4
2
Returns: 10
6
4
3
Returns: 10
6
4
4
Returns: 5
6
4
5
Returns: 26
6
5
0
Returns: 0
6
5
1
Returns: 0
6
5
2
Returns: 0
6
5
3
Returns: 0
6
5
4
Returns: 0
6
5
5
Returns: 1
7
0
0
Returns: 1
7
6
0
Returns: 0
7
0
1
Returns: 0
7
6
6
Returns: 1
7
0
0
Returns: 1
7
6
1
Returns: 0
7
1
4
Returns: 15
7
2
1
Returns: 156
7
2
2
Returns: 180
8
0
0
Returns: 1
8
7
0
Returns: 0
8
0
1
Returns: 0
8
7
7
Returns: 1
8
0
3
Returns: 0
8
0
6
Returns: 0
8
0
2
Returns: 0
8
7
2
Returns: 0
8
6
2
Returns: 21
9
0
0
Returns: 1
9
8
0
Returns: 0
9
0
1
Returns: 0
9
8
8
Returns: 1
9
6
7
Returns: 960
9
1
2
Returns: 28
9
4
2
Returns: 16912
9
4
1
Returns: 19328
9
6
8
Returns: 4293
10
0
0
Returns: 1
10
9
0
Returns: 0
10
0
1
Returns: 0
10
9
9
Returns: 1
10
4
8
Returns: 140571
10
8
0
Returns: 1
10
1
1
Returns: 9
10
5
0
Returns: 88234
10
7
6
Returns: 5124
11
0
0
Returns: 1
11
10
0
Returns: 0
11
0
1
Returns: 0
11
10
10
Returns: 1
11
8
7
Returns: 14880
11
10
7
Returns: 0
11
10
2
Returns: 0
11
7
3
Returns: 200640
11
0
8
Returns: 0
12
0
0
Returns: 1
12
11
0
Returns: 0
12
0
1
Returns: 0
12
11
11
Returns: 1
12
5
10
Returns: 14413894
12
6
6
Returns: 13547688
12
11
8
Returns: 0
12
4
0
Returns: 9738114
12
8
11
Returns: 2203488
13
0
0
Returns: 1
13
12
0
Returns: 0
13
0
1
Returns: 0
13
12
12
Returns: 1
13
10
9
Returns: 111320
13
11
10
Returns: 66
13
7
11
Returns: 116857368
13
8
3
Returns: 32376960
13
1
8
Returns: 495
14
0
0
Returns: 1
14
13
0
Returns: 0
14
0
1
Returns: 0
14
13
13
Returns: 1
14
3
12
Returns: 6217523
14
2
3
Returns: 290862
14
7
13
Returns: 2275172004
14
3
2
Returns: 12064494
14
8
6
Returns: 917857512
15
0
0
Returns: 1
15
14
0
Returns: 0
15
0
1
Returns: 0
15
14
14
Returns: 1
15
9
11
Returns: 6808511892
15
11
1
Returns: 20716164
15
1
0
Returns: 16369
15
1
11
Returns: 364
15
12
5
Returns: 1057056
16
0
0
Returns: 1
16
15
0
Returns: 0
16
0
1
Returns: 0
16
15
15
Returns: 1
16
9
6
Returns: 200590204815
16
11
7
Returns: 5324138820
16
5
13
Returns: 49225573425
16
13
2
Returns: 858795
16
10
3
Returns: 48934105675
17
0
0
Returns: 1
17
16
0
Returns: 0
17
0
1
Returns: 0
17
16
16
Returns: 1
17
9
4
Returns: 4895505762420
17
6
14
Returns: 1849800604560
17
5
5
Returns: 337016451408
17
11
11
Returns: 337016451408
17
15
5
Returns: 4368
18
0
0
Returns: 1
18
17
0
Returns: 0
18
0
1
Returns: 0
18
17
17
Returns: 1
18
8
5
Returns: 103660861127460
18
13
13
Returns: 147322940100
18
9
13
Returns: 103571963386500
18
7
9
Returns: 55931879316170
18
10
15
Returns: 56326385238104
19
0
0
Returns: 1
19
18
0
Returns: 0
19
0
1
Returns: 0
19
18
18
Returns: 1
19
12
2
Returns: 132727309797744
19
10
12
Returns: 1466882440737168
19
1
17
Returns: 18
19
15
12
Returns: 13204647456
19
17
5
Returns: 8568
20
0
0
Returns: 1
20
19
0
Returns: 0
20
0
1
Returns: 0
20
19
19
Returns: 1
20
14
14
Returns: 93376455494040
20
3
4
Returns: 54981145272
20
18
7
Returns: 50388
20
2
19
Returns: 524268
20
2
17
Returns: 22410405
20
2
0
Returns: 1151775897
20
2
13
Returns: 223432020
20
3
0
Returns: 251732291184
20
3
6
Returns: 52803592968
20
6
0
Returns: 2527925001876036
20
6
9
Returns: 1079711852655436
20
11
0
Returns: 11485644635009424
20
11
17
Returns: 19526981818872618
20
13
0
Returns: 278794377854832
20
13
18
Returns: 768689550213368
20
15
0
Returns: 251732291184
20
15
17
Returns: 2565372860370
20
17
0
Returns: 524268
20
17
16
Returns: 63491787
20
19
0
Returns: 0
20
19
12
Returns: 0
20
10
0
Returns: 27862280567093358
20
11
7
Returns: 19426402481860296
20
10
10
Returns: 33978309097618600
20
10
3
Returns: 34032711993560508
20
7
0
Returns: 11485644635009424
20
9
9
Returns: 33978309097618600
20
10
4
Returns: 33962888646873552