TopCoder Statistics - Problem Statement

Problem Statement

King Dengklek is the first king of the Kingdom of Ducks. The kingdom consists of N cities, conveniently numbered 0 through N-1. The first M cities (i.e., cities 0 through M-1) are restricted cities.

Initially, there are no roads in the kingdom, so no two cities are connected. King Dengklek wants to connect the cities using exactly K bidirectional roads, such that:

There is at most one road connecting each pair of cities.
No road connects a city to itself.
Each restricted city is connected to exactly two other cities.
For each pair of cities, there is at least one path (i.e., a sequence of consecutive roads) connecting them.

You are given the ints N, M, and K. Return the number of different ways King Dengklek can build the roads, modulo 1,000,000,007. Two ways are different if there is a pair of cities that is connected in one way but not connected in the other way.

Definition

Class:: KingdomAndCities
Method:: howMany
Parameters:: int, int, int
Returns:: int
Method signature:: int howMany(int N, int M, int K)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
M will be between 0 and 2, inclusive.
M will be less than or equal to N.
K will be between 1 and 50, inclusive.

Examples

3

0

3

Returns: 1

Here is the only possible way.
4

1

4

Returns: 9

Here are the nine possible ways. The restricted city (city 0) is colored blue.
5

2

11

Returns: 0

There are too many roads to build.
5

0

8

Returns: 45
10

2

20

Returns: 150810825
1

0

1

Returns: 0
1

1

1

Returns: 0
2

0

1

Returns: 1
2

2

2

Returns: 0
2

1

1

Returns: 0
5

2

3

Returns: 0
5

0

3

Returns: 0
6

1

4

Returns: 0
6

2

4

Returns: 0
6

0

4

Returns: 0
16

0

49

Returns: 48360829
49

1

29

Returns: 0
25

1

33

Returns: 506402538
8

1

8

Returns: 578907
4

2

34

Returns: 0
28

0

4

Returns: 0
29

0

13

Returns: 0
11

0

31

Returns: 856255304
14

0

1

Returns: 0
31

1

35

Returns: 639226707
10

2

42

Returns: 0
8

2

46

Returns: 0
39

0

19

Returns: 0
23

2

29

Returns: 200458943
30

2

35

Returns: 409602685
14

0

6

Returns: 0
19

1

46

Returns: 905919826
33

1

8

Returns: 0
16

0

33

Returns: 368947806
16

1

3

Returns: 0
2

1

40

Returns: 0
43

2

25

Returns: 0
41

1

35

Returns: 0
11

0

3

Returns: 0
39

0

27

Returns: 0
26

2

26

Returns: 85272996
33

2

6

Returns: 0
28

0

46

Returns: 828756516
35

2

1

Returns: 0
17

1

38

Returns: 591679493
22

1

35

Returns: 483487378
11

0

41

Returns: 547303434
36

2

35

Returns: 170513612
44

0

38

Returns: 0
35

2

9

Returns: 0
41

2

13

Returns: 0
27

1

36

Returns: 827423461
7

2

30

Returns: 0
38

2

37

Returns: 362211780
13

1

28

Returns: 471304464
19

0

41

Returns: 319153854
21

1

31

Returns: 536604856
11

2

23

Returns: 719296228
50

0

50

Returns: 921061336
50

1

50

Returns: 261563447
50

2

50

Returns: 654698051

Statistics

Problem Statement for "KingdomAndCities"

Problem Statement

Definition

Constraints

Examples