Problem Statement
Given a tree with N vertices, we can try coloring its vertices using C colors. The standard constraint for graph coloring applies: adjacent vertices cannot share the same color.
Of course, some of those colorings can look more boring than others. What's the point of being allowed to use C colors if you aren't actually going to use them all?
A pretty C-coloring of a tree is a coloring of its vertices such that neighbors never share the same color, and each color appears in the tree at least once.
Let num(T, C) be the number of such colorings for the specific tree T. Let minC(N, C) and maxC(N, C) be the minimum and maximum of num(T, C) over all trees T with exactly N vertices.
Return a
Definition
- Class:
- ColorfulTrees
- Method:
- count
- Parameters:
- int, int
- Returns:
- int[]
- Method signature:
- int[] count(int N, int C)
- (be sure your method is public)
Constraints
- N will be between 1 and 10^9, inclusive.
- C will be between 1 and 10^6, inclusive.
Examples
4
2
Returns: {2, 2 }
Each tree on 4 vertices is isomorphic either to the 1-2-3-4 path, or to a star with one vertex in the middle connected to each of the other three. Both of these trees happen to have exactly two pretty 2-colorings: for the path it's the colorings A-B-A-B and B-A-B-A, for the star the colorings are: B-A-B A-B-A | | B A
15
15
Returns: {674358851, 674358851 }
As each color must appear exactly once, it should be clear that the colors must form a permutation. On the other hand, if all colors are distinct then we don't actually care about the shape of the tree, as regardless of the shape it is already guaranteed that no two neighbors will share the same color - i.e., we already know that the coloring will be valid. Don't forget to use the proper modular arithmetic when computing the answer.
42
47
Returns: {0, 0 }
Working out what's going on in this test case really isn't that hard: you cannot use each of 47 colors at least once if you have fewer than 47 vertices.
1
1
Returns: {1, 1 }
1
2
Returns: {0, 0 }
1
47
Returns: {0, 0 }
2
1
Returns: {0, 0 }
2
2
Returns: {2, 2 }
2
3
Returns: {0, 0 }
2
47
Returns: {0, 0 }
3
1
Returns: {0, 0 }
3
2
Returns: {2, 2 }
3
3
Returns: {6, 6 }
3
4
Returns: {0, 0 }
3
42
Returns: {0, 0 }
987654
976543
Returns: {180574822, 180574822 }
25
15
Returns: {985320689, 985320689 }
987651234
989899
Returns: {559381954, 559381954 }
464646
875645
Returns: {0, 0 }
12536778
1
Returns: {0, 0 }
647855858
2
Returns: {2, 2 }
432643463
5566
Returns: {878309876, 878309876 }