まずは順列 \(P\) が固定である場合のスコアを計算してみましょう。 \(P\) を適当に選んで何回か実験を行うと、観察から次の事実が分かると思います。

• 紙に \(1\) から \(N\) の数字を書き、それぞれの人からボールを渡す相手に矢印を引くと、いくつかのループに分かれることがわかる。
  このとき、すべてのループの大きさに対して最小公倍数を取ったものが順列のスコアになる。

  • 例えば \(N = 5, P = (2,5,4,3,1)\) の場合、 \(3 \to 4 \to 3\) というループと \(1 \to 2 \to 5 \to 1\) というループに分かれ、スコアは \(\mathrm{lcm}(2, 3) = 6\) になる。
    

証明は最小公倍数の性質から従います。また、このようなループを 巡回置換 と呼びます。

次は \(S(P)^K\) の和を取ることを考えてみましょう。もちろん愚直にすべての \(P\) に対して実験すると \(N\) に対して指数時間かかってしまうので、何らかの工夫を行って計算量を落とす必要があります。ここではこの問題を 動的計画法(DP) で解くことを考えてみましょう。

本題に入る前にまずは一般論を述べると、この問題に限らず、 DP で計算量を落とす場合には「同一視してよい部分はどこか」という点に注目することが大切です。複数の状態を 1 つの状態にまとめることで計算量を落とすのは DP の典型的な手法の 1 つで、ここを抑えておくと解ける問題の幅が広がると思います。

さて、この問題においてスコアの計算に重要なのは「ループの長さ」で、「誰が誰にボールを渡して、どの長さのループに所属している」といった属人的な情報は要らないことが容易にわかります。よってこの問題では、ループの長さのみを持った DP を行い、「〇〇のループを持ったものが何通りあって、そのときのスコアは〇〇」 という風にまとめるのがよいとわかります。

DP を行うための部分問題として、長さ \(N\) の順列 \(P\) のうち長さ \(k_1, k_2, \dots, k_m\) の巡回置換に分割できるものの個数を考えてみましょう。

この問題はここから二項係数を用いた複雑な考察が必要になり、おそらくこの部分で脱落した人も多いのではないかと思います。このような状況に遭遇したとき、自分の場合は経験上「具体例を挙げて、それに合致する一般的な式を立てる」という方法でどうにか乗り切れることが多いので、この手の問題で苦労するタイプの人は試してみるとよいと思います。また、どこが間違っているか分からない場合は以下のコードのように 愚直解法と比較してミスを探す のも 1 つの典型的な手法です。

def naive(N, k):
  # 愚直解法を書く
  return 答え

def calc(N, k):
  # 自分の思いついた式を書く
  return 答え

while True:
  # N, k を乱数で生成する (N は naive が動く程度の大きさ)
  assert naive(N, k) == calc(N, k)

先に答えを書きます。まず、巡回置換の長さ \(k_1, k_2, \dots, k_m\) を、長さ \(L_i\) のループが \(F_i\) 個、といった頻度列に変換します。このとき

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

が答えになります。

式の意味を簡単に説明すると次のようになります。(いくつかの具体例で実験していくのが分かりやすいと思います。)

• \(N!\) の部分と \(\prod\) の中の \(\frac{1}{(L!)^F \cdot F!}\) の部分は \(N\) 個の頂点をどのようにグループ分けするかを意味しています。
• 後ろの \(((L-1)!)\) の部分は、 \(L\) 個の頂点があったときにそれらが巡回置換をなすように矢印を張る方法の数です。長さ \(L\) のループが \(F\) 個あるのでこれを \(F\) 乗したものを掛けています。

これがわかれば、あとは DFS などを用いて分割の方法を DP で列挙していけばよいです。

DFS の計算量は \(N\) を いくつかの整数に分ける方法の場合の数に依存するとわかります。この数は \(N = 50\) でも \(204226\) と十分小さいので、DFS は十分高速に動くとわかります。(ちなみにこれは分割数 (partition number) と呼ばれる数です。) 以上よりこの問題を解くことができました。