Contest Duration: - (local time) (100 minutes) Back to Home
Official

F - Cube Editorial by en_translator

We number each face of the cube in the following way, just as a dice, and we denote each face by Surface 1 and so on.

There are 24 ways to rotate a cube since there are 6 ways to turn Surface 1 to, and 4 ways to turn Surface 2 to.

Solution 1: Pólya Enumeration Theorem

Pólya enumeration theorem claims that “the number of combinations of integers to write, where two combinations are identified if they coincide after any rotation” is equal to the average of, for each way of rotation, “the number of combinations which are invariant by the rotation.” (We don’t prove this here.)

Therefore, we can solve the original problem if we can find, for each of 24 rotations, “the number of combinations of integers to write which are invariant by the rotation.”

For example, let us consider rotating it by the axis through the centers of Surface 1 and 6 by 90 degrees clockwise. In order to be invariant by the rotation, Surface 2, 3, 4 and 5 should have the same numbers. The number of such combinations is equal the number of tuples of positive integers $$(x, y, z)$$ where $$x + y + 4z = S$$, where $$x, y,$$ and $$z$$ corresponds to the numbers written on Surface 1, 6, and 2, respectively (Note that we don’t care if $$x, y,$$ and $$z$$ are distinct or not). This number can be found with a digit DP or fast matrix exponentiation. (described later)
Same facts apply for the other rotations.

Therefore, we’ve seen that we can count the number of combinations that are invariant by a rotation, so the problem has been solved by Pólya enumeration theorem.

Solution 2: Division into Cases

First, let us consider how many ways are there to write numbers in surface, once the 6 numbers to write has been determined. This can be found by first enumerating all the permutations of these numbers assigned to each face, and then removing those which coincide after a rotation of the cube.

Given six integers to write, the number of ways to write them is dependent only on how many same numbers there are. For example, the number of ways to write $$(1,1,1,2,2,3)$$ and $$(1,2,2,2,3,3)$$ is the same. Therefore, it is sufficient to find the number of 6-tuple of positive integers whose sum is $$S$$ for each of such types.

Let us denote 6 integers to write on the cube by $$x_1\leq x_2 \leq x_3\leq x_4 \leq x_5 \leq x_6$$. Each of these $$5$$ inequality is either a strict inequality or an equality, so we have $$32$$ cases in total.

For instance, let us consider the number of combinations of positive integers such that $$x_1=x_2 < x_3=x_4=x_5 <x_6$$ and $$x_1+x_2+x_3+x_4+x_5+x_6=S$$.

Assuming $$x_0=0$$ for convenience, and with variable transformations $$y_i=x_i-x_{i-1}$$, the number of such combinations is equal to the number of tuples of positive integers $$(y_1,y_3,y_6)$$ such that $$6y_1 +4y_3+y_6=S$$. The number of such solutions can be found with a digit DP or fast matrix exponentiation. (desribed later)
Same facts apply for the other cases.

Since we found the number of tuples for each type, the original problem has been solved by multiplying each of them by the number of ways to write on the cube.

This solution is by evima.

Solution 3: OEIS

Obviously, the answer for $$S=6,7$$ is $$1$$, and the answer for $$S=8,9$$ can be found in the samples. If we search “1,1,3,5 cube” in The On-Line Encyclopedia of Integer Sequences, we can find A54473. Since it has the generating function of the sequence, we can find the answer in an $$O(\log S)$$ time.

For digit-DP / fast matrix exponentiation part

For instance, let us consider finding the number of combinations of positive integers that satisfies $$x+y+4z=S$$ (it can be found for other cases similarly). With $$x,y,$$ and $$z$$ subtracted by $$1$$, and substituting $$S-6$$ with $$S$$, it can be boiled into the problem “find the number of combinations of non-negative integers that satisfies $$x+y+4z=S$$.” We consider this.

By digit DP

Let us consider the following DP:

dp[ $$i$$ ][ $$j$$ ]= the number of tuples of non-negative integers $$(x, y, z)$$ with $$i$$ or less digits, such that the last $$i$$ digits of $$x + y + 4z$$ are equal to those of $$S$$, and $$j$$ is carried to the next digit

This time, the carry is at most $$t$$, so we only have to consider the range $$0 \leq j \leq 5$$. If we count the number of tuples of integers between $$0$$ and $$9$$ (inclusive) such that $$a+b+4c=X$$ for each $$X$$, the transitions can be performed fast.

By fast matrix exponentiation

Let $$a_s$$ be the number of combinations of non-negative integers such that $$x+y+4z=S$$. By inclusion-exclusion principle, we obtain a recurrence relation $$a_S=a_{S-1}+a_{S-1}+a_{S-4}-a_{S-1-1}-a_{S-1-4}-a_{S-1-4}+a_{S-1-1-4}$$. By applying fast matrix exponentiation properly, we can find the $$S$$-th term of the sequence that satisfies this recurrence relation in an $$O(\log S)$$ time.

posted:
last update: