SRM700 Div1Medium. CrazyFunctions
整数 ,
が与えられる。以下の条件を満たす関数
を数え上げよ。
の定義域および値域は 1以上n以下の整数である。
を満たす。関数
の定義は以下の通り。
は
の最小値を返す関数。
は任意の非負整数。
の要素数。
について、関数
の取りうる値の集合。
とは、関数
に
回適用した値。
、および
を満たす。
制約
問題を理解する
関数f(1)〜f(n)の値を決めることは、n頂点の出次数が1である有向グラフ*1*2 を考えることと同一視できる。例えば、n = 3、f(1) = 2, f(2) = 3, f(3) = 3 なら次の図のようになる。
この問題は (ごちゃっとした条件を満たす) n頂点のラベル付き関数グラフを数え上げなさい という問題に言い換えられる。以降、ごちゃっとした条件 について順番に検討していこう。
,
とは、1〜nに対して、関数を
を w 回 以上 適用した時に取る値の集合である。関数グラフで言い換えると、これは任意の頂点からはじめて、辺を w 回以上辿ったときに訪れる頂点の集合になる。また、
はその頂点たちの数である。
とは、負でない整数 w を取ったときの
の最小値である。
において、w を増やすと訪れる頂点は減るので、
の値は w をどんどん増やした時、
が収束する値となる。関数グラフはどこかに閉路ができるので、
の最小値はその閉路の大きさと等しい。
つまり
となるような
はいくつあるか？ => 長さ 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
- =>
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でサラッと紹介されてて、これで後半パートを解いている。解説仕事しろ。
頂点を根に持つ ラベル付き
頂点の森は
通りある。
ケイリーの公式 は の特別なバージョンである。
- ラベル付き
通りある。
