Problem Statement
Bob is going to create a graph with N nodes. The graph will be constructed in two steps. First, Bob will take N isolated vertices, label them 1 through N and color each of them using one of K colors. Then, Bob will add some directed edges to the graph. For each i between 2 and N, inclusive, Bob may choose a single value j < i such that the nodes i and j have different colors. If he does, he will add the edge from i to j to his graph. Note that Bob may choose not to add any edge from node i, even if there are some valid choices of j.
Two graphs are considered the same if they have the same node colors and the same set of edges.
You are given the
Definition
- Class:
- ColorfulLineGraphsDiv2
- Method:
- countWays
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int countWays(int N, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 100, inclusive.
- K will be between 1 and 3, inclusive.
Examples
3
2
Returns: 24
The 24 different graphs are shown below. In each picture, the vertices have labels 1, 2, 3 from the left to the right.
15
2
Returns: 789741546
100
1
Returns: 1
1
3
Returns: 3
100
3
Returns: 492594064
16
3
Returns: 434231843
22
3
Returns: 589570488
46
3
Returns: 265705562
93
3
Returns: 157695640
90
2
Returns: 166267694
51
2
Returns: 948537388
89
2
Returns: 749079870
62
3
Returns: 231620408
99
3
Returns: 873097489
49
3
Returns: 196932377
26
3
Returns: 568243825
59
2
Returns: 16340084
19
2
Returns: 146326063
95
3
Returns: 654868516
91
3
Returns: 550228583
12
3
Returns: 853525290
24
3
Returns: 780824365
76
2
Returns: 661063309
10
3
Returns: 749310484
73
3
Returns: 632284981
16
3
Returns: 434231843
22
3
Returns: 589570488
46
3
Returns: 265705562
93
3
Returns: 157695640
90
2
Returns: 166267694
51
2
Returns: 948537388
89
2
Returns: 749079870
62
3
Returns: 231620408
99
3
Returns: 873097489
49
3
Returns: 196932377
26
3
Returns: 568243825
59
2
Returns: 16340084
19
2
Returns: 146326063
95
3
Returns: 654868516
91
3
Returns: 550228583
12
3
Returns: 853525290
24
3
Returns: 780824365
76
2
Returns: 661063309
10
3
Returns: 749310484
73
3
Returns: 632284981