First, consider computing the score for a fixed permutation \(P\). Choose arbitrarily some number of \(P\)’s, and you will see the fact from the observation:

• If you write numbers from \(1\) through \(N\), and an arrow to whom each person is going to pass balls, then it can be divided into loops.
  Then, the score for the permutation is the least common multiplier (LCM) of the size of all loops.

  • For example, when \(N = 5\) and \(P = (2,5,4,3,1)\), it is divided into two loops, \(3 \to 4 \to 3\) and \(1 \to 2 \to 5 \to 1\), and the score is \(\mathrm{lcm}(2, 3) = 6\).
    

The proof follows from the property of LCM. Also, such a loop is called a cyclic permutation.

Next, consider how to find the sum of \(S(P)^K\). Of course, if you try every \(P\), it requires a exponential time of \(N\), so we should reduce the time complexity. Here, we consider solving this problem with DP (Dynamic Programming).

Before getting down to business, let us state the general rule, not limited to this problem: when trying to reduce the time complexity with DP, it is important to focus on “what aspect can be identified.” It is a very common technique to equate multiple states into one to reduce the computational complexity, enabling us to solve more problems.

Now, in this problem, it can be easily understood that the important factor for the score is “the lengths of the loops,” but not person-specific information like “who passes balls to whom, and which loop they belong.” Therefore, in this problem, it is a good idea to do DP in which only the lengths of loops are stored, and process as “there are this number of permutations that generate this kind of loop, and they yield this score.”

As a subproblem for computing DP, let us consider how many permutations \(P\) of length \(N\) can be represented as cyclic permutations of lengths \(k_1, k_2, \dots, k_m\).

From now on, this problem requires a complex observation using binomial coefficients, and some of you might have dropped out because of this. When encountered to such situation, in my experience it can often be barely overcome by “make some specific examples and construct a generic formula that matches them”, which is recommended for other people who are not good at it as well. Also, if you have no idea why it is wrong, it is typical to compare with a naive solution and look for the mistakes like the code below.

def naive(N, k):
  # Write a naive solution
  return answer

def calc(N, k):
  # Write the formula you came up with
  return answer

while True:
  # Generate N and k as random numbers
  assert naive(N, k) == calc(N, k)

I will tell you the answer first. Transform the lengths of cyclic permutations \(k_1, k_2, \dots, k_m\) to the sequence of occurrences in the format of “there are \(F_i\) loops of length \(L_i\).” Then, the answer is

\[ N! \times \prod_{L,F} \frac{1}{(L!)^F \cdot F!} \times ((L-1)!)^F.\]

The formula can be explained as follows. (It may make easier to understand to check for some specific examples.)

• \(N!\) and \(\frac{1}{(L!)^F \cdot F!}\) inside \(\prod\) represents how to divide \(N\) vertices into groups.
• The final \(((L-1)!)\) part correspond to the number of ways to add arrows to \(L\) vertices so that they form a cyclic permutation. Since there are \(F\) loops of length \(L\), we multiply its \(F\)-th power.

Once we found it, all that left is to enumerate the ways of divisions by DP , with the techniques like DFS (Depth-First Search).

We can see that the complexity of DFS depends on the number of ways to divide \(N\) into some number of integers. The number is fairly as small as \(204226\) even for \(N = 50\), so we can see that the DFS works fast enough. (By the way, this is called “partition number”.) Hence, the problem has been solved.