Author: Anton Trygub
Solved by:
First to solve: N/A
Let's start from creating nodes , , , and connecting them into triangle — we suppose from now on that the first node is colored in color , the second in color , third in color , and we need to construct a graph such that the rest is colorable in exactly ways.
Let's create nodes, connect st of them to , nd to , rd to , th to , and so on by cycle. This way, the st node can only be colored in one of colors , nd — in one of , rd — in one of , th - and so on
Now, connect the -th of these nodes to the (i+1)-st of them, in a chain. Note that this configuration has exactly valid colorings: some prefix of nodes will be colored in the left color from the pair, and the remaining will be colored in the right color from the pair.
This is the end of the "template".
Now, for the -th node let's create a_i nodes which are connected both to it and to the left color of this node (for example, for the first node, to node 1 of the starting triangle. Note that if the first nodes are colored in their left colors, then there are exactly 2^{a_1 + ... + a_k} ways to color these new nodes. So, the total number of colorings will be 1 + 2^{a_1} + 2^{a_1 + a_2} + ... + 2^{a_1 + ... + a_n}.
Now the solution is easy: while is even, divide it by , and add a leave hanging from node (this just multiplies number of ways to color by ). Then, let be the number of bits which are on in (not counting the smallest bit) — then create an edge from node 3+b to the right node in its pair — this will leave only b+1 ways to color. Then just add additional (highest bit) nodes, as shown above, and connect remaining nodes to and .