A colleague had a coding interview for Huawei last Sunday. I heard the second question was quite “mathematical”. Let me rephrase it here a little bit.

A hero summoner in a MOBA game has an ability to manipulate three elements. By controlling the order of releasing these elements, he can cast different spells accordingly. For example, casting in the order of fire, water, lightening can be treated as a spell. But there are some limitations as well.

Consider fitting the elements of that spell in a cycle. Then turning the cycle clockwise or counterclockwise does not produce any new spells. Additionally, inverting the cycle will not generate new ones either. The question is, if n is the number of elements he is capable of mastering, m is the number of elements consisting a spell, then what is the value of the number of different spells modulo 1000000007?

Typically, the mathematical term that describes the way of ordering elements, is called Circular Permutation.

The number of ways to arrange n distinct objects along a fixed (i.e., cannot be picked up out of the plane and turned over) circle is

$$ P_n=(n-1)!$$

The reason why it is the factorial of n-1 instead of $n$ is all cycle rotation.

perm

If we consider a stricter definition, there will be only three free permutations (i.e., inequivalent when flipping the circle is allowed).

$$P’_n=\frac{1}{2} (n-1)!, n\geq 3$$

In our problem, the number would be

$${n \choose m} \frac{1}{2} (m-1)!$$

Since \(1\leq m \leq 10000, 1\leq n \leq 20000\), direct calculation of factorial is suicidal for a computer. The hack here should be using modulo arithmetic, namely, we only keep the mod of \(10^9 + 7\) in intermediate steps.

fact <- function(n) {
  res <- 1
  for (i in 1:n) {
    res <- (res * i) %% 1000000007
  }
  return(res)
}

Although factorial(203) will give us Inf as a result, fact(203 won’t. It will give us an exact answer of 572421883.