PROBLEM LINK:
Author: Misha Chorniy
Tester: Mugurel Ionut Andreica
Editorialist: Mugurel Ionut Andreica
DIFFICULTY:
HARD
PREREQUISITES:
PROBLEM:
Count the number of colorings with C colors of the faces of a polyhedron, where two colorings are equivalent if one can be obtained from the other by using rotations or mirroring.
EXPLANATION:
This is an application of Burnside’s lemma, which states that the total number of (non-equivalent) colorings is equal to the average number of fixed points of the group of permutations which define the equivalence relationships.
An equivalence permutation (p(1), …, p(N)) has the meaning that any two colorings of the faces 1, …, N in which each pair of faces (i,p(i)) has the same color are equivalent.
So the general solution for this problem looks like this:
Step 1. Find all the equivalence permutations.
Step 2. For each such permutation compute its number of fixed points.
Step 3. Add up all the numbers computed at Step 2 and then divide the sum by the total number of equivalence permutations. This will be the answer for this problem.
Let’s see how to handle each of the 3 steps:
Step 1
An equivalence permutation is an automorphism of the graph defined by the faces of the polyhedron as nodes and the adjacency between them as edges. That is, a permutation (p(1), …, p(N)) is an equivalence permutation if for every pair (i,j) we have that Adjacent(i,j)=Adjacent(p(i),p(j)) (i.e. if the faces i and j are adjacent, then so must be the faces p(i) and p(j); if the faces i and j are not adjacent then the faces p(i) and p(j) must also not be adjacent).
In order to generate all these permutation we can use recursive backtracking. When adding a new element p(i) to the permutation we first check that the prefix p(1), …, p(i) satisfies the adjacency rules mentioned above (i.e. we check the pairs of faces (k,i) with 1\leq k\leq i-1 to see if they satisfy the adjacency conditions). Only if the adjacency conditions are satisfied do we continue to the next element of the permutation.
You need to take a small leap of faith to implement this to verify that this backtracking approach is actually very fast.
Step 2
Let’s compute the number of fixed points of a permutation (p(1), …, p(N)). A fixed point is a coloring of the faces (col(1), …, col(N)) which, when we permute the order of the faces according to the permutation p, we obtain the exact same sequence of colors (i.e. (col(1), …, col(N)) = (col(p(1)), …, col(p(N)))).
The number of fixed points of a permutation is related to the number of cycles of a permutation. Basically, every element in the same cycle of the permutation must be assigned the same color in order for the coloring to be a fixed point for the permutation. This means that for every cycle we can choose the color of all of its elements to be any of the C colors, but once the color is chosen, we need to assign it to all the elements in the cycle. Once we know this it’s easy to see that the number of fixed points of a permutation is C^{numCycles}, where numCycles is the number of cycles of the permutation (don’t forget to compute this number modulo 10^9+7).
Step 3
Adding up all the values from Step 2 is straight-forward (don’t forget to add them up modulo 10^9+7). In order to divide the sum by the total number of permutations NP we need to find NP^{-1} = the inverse of NP modulo 10^9+7. Since 10^9+7 is a prime number we have that NP^{-1} = NP^{10^9+5} (modulo 10^9+7). Then, dividing by NP is actually equivalent to multiplying by NP^{-1}.
TESTER’S SOLUTIONS:
Tester’s solution can be found here.