読者です 読者をやめる 読者になる 読者になる

問題解決の宝石箱

競技プログラミング/数学ネタ置き場

SRM700 Div1Medium. CrazyFunctions

SRM700 Div1Medium. CrazyFunctions

整数  {n},  {k} が与えられる。以下の条件を満たす関数  {f} を数え上げよ。

  •  {f} の定義域および値域は 1以上n以下の整数である。
  •  {Z(f) = k} を満たす。関数  {Z} の定義は以下の通り。
    •  {Z(f)} {S(f, w)} の最小値を返す関数。 {w} は任意の非負整数。
    •  {S(f, w)} は 集合  {G(f, w)} の要素数
    •  {G(f, w)} {w} 以上の整数  {r} について、関数  { f^{r}(x)} の取りうる値の集合。
      •  { f^{w}(x)} とは、関数  {f}{x}{w} 回適用した値。 {f^{0}(x) = x}、および  {f^{j+1}(x) = f^{j}(f(x))} を満たす。

制約

  •  {1 \leq n \leq 5000}
  •  {1 \leq k \leq n}

問題を理解する

関数f(1)〜f(n)の値を決めることは、n頂点の出次数が1である有向グラフ*1*2 を考えることと同一視できる。例えば、n = 3、f(1) = 2, f(2) = 3, f(3) = 3 なら次の図のようになる。

f:id:hama_DU:20161029202801p:plain

この問題は (ごちゃっとした条件を満たす) n頂点のラベル付き関数グラフを数え上げなさい という問題に言い換えられる。以降、ごちゃっとした条件 について順番に検討していこう。

 {G(f, w)} ,  {S(f, w)}

 {G(f, w)} とは、1〜nに対して、関数を  {f} を w 回 以上 適用した時に取る値の集合である。関数グラフで言い換えると、これは任意の頂点からはじめて、辺を w 回以上辿ったときに訪れる頂点の集合になる。また、 {S(f, w)} はその頂点たちの数である。

 {Z(f)}

 {Z(f)} とは、負でない整数 w を取ったときの  {S(f, w)} の最小値である。 {S(f, w)} において、w を増やすと訪れる頂点は減るので、 {Z(f)} の値は w をどんどん増やした時、 {S(f, w)} が収束する値となる。関数グラフはどこかに閉路ができるので、 {S(f, w)} の最小値はその閉路の大きさと等しい。

つまり

 {Z(f) = k} となるような  {f} はいくつあるか? => 長さ k の閉路を含む関数グラフはいくつあるか?である。問題をシンプルなグラフの形に帰着できた。

解法

閉路を作る方法の数え上げ

まず、閉路に使う k 頂点を決める。頂点の選び方は  {\binom{n}{k}} 通り存在する。そして、これらを使った閉路の作り方は  {k!} 通りある。*3

有向森の数え上げ

残りの問題は、残りの n-k 頂点を使ったグラフを数え上げる部分である。

dp[x] := <これまで(根を含んで) x 頂点を使ったとき、グラフは何通りあり得るか> を考える。初期値は dp[k] = 1、求めたい値は dp[n]dp[x] の値を求めるときは、x-k頂点を使ってグラフを構築する方法を計算する。このとき、くっ付ける葉の頂点のパターンを考える。

具体例を上げる。 n=6, k=3 とし、残りの頂点が {4, 5, 6} と番号付けされているとする。以下、葉となる頂点の集合を X としたとき、木の作り方のパターンを ptn(X) で表す。

  • {4, 5, 6} が葉になる場合 (図A)、パターンはそれぞれの葉の辺がどの根に向くか、なので
    • => ptn({4, 5, 6}) = 3^3
  • {4, 5} が葉になる場合 (図B)、 4頂点の木の作り方 dp[4] に4頂点への辺の向き方 4^2 を掛け
    • => ptn({4, 5}) = dp[4] * 4^2
  • {4} が葉になる場合 (図C)、 dp[5] に 5 を掛ける。
    • => ptn({4}) = dp[5] * 5

f:id:hama_DU:20161029202818p:plainf:id:hama_DU:20161029202820p:plainf:id:hama_DU:20161029202822p:plain

ptn({4, 5})ptn({4, 5, 6}) 等には同じグラフが含まれるが、これには包除原理が適用できる。実際、n=6, k=3 の例で足し引きのパターンを合計すると dp[6] = ptn({4}) + ptn({5}) + ptn({6}) - ptn({4, 5}) - ptn({4, 6}) - ptn({5, 6}) + ptn({4, 5, 6}) となり*4、葉となる頂点数ごとにプラス、マイナスが交互に出現する形になっている。当然、ptn({4}) = ptn({5}) = ptn({6}) 等が成り立つので、これらはまとめて計算できる。

備考

ちなみにこの問題の後半パート、「k 頂点を根とする森の数え上げ」には公式が存在する。Editorialでサラッと紹介されてて、これで後半パートを解いている解説仕事しろ。

  •  {k} 頂点を根に持つ ラベル付き  {n} 頂点の森は  {k n^{n-k-1}} 通りある。

ケイリーの公式 {k=1} の特別なバージョンである。

  • ラベル付き  {n} 頂点の木は  { n^{n-2} } 通りある。

解答コード

SRM700 Div1Medium

*1:以降、これを関数グラフ(英:Functional Graph)と呼ぶ

*2:日本語訳は適当。教科書や論文等で使われてる日本語があったら教えてほしいです

*3:実験して。

*4:不安なら確認しよう。