CODE FESTIVAL 2017 Elimination Tournament F-Unicyclic Graph Counting を時間計算量 で解く解法を紹介します。
問題リンク
問題概要
長さ の正整数列 が与えられる。頂点 の次数が であるような 頂点 辺の単純連結グラフの個数を で求めよ。
定式化
まず、 となる頂点しか存在しない場合、解は です。以下、 を満たす頂点が存在するとします。
頂点の集合の中から、サイクルとして選択する頂点の集合を 、選択しない頂点の集合を とします。また、 とします。
ここで、 とします。(前提より、この仮定を満たさない について、解は です)
また、いったん 、 としておきます。
この時の解は(サイクルの作り方) (サイクルを つの頂点としてみた時の木の数) (サイクルから出る辺と頂点の対応付け) の形で書け、
と表せます。これを変形すると
となります。この式では や のケースが を返すので、さっきの つの仮定は取り除いて ok です。
ここで、 とします。
すべての について、 の部分集合 についての が求まれば、解は高速に求まります。
ここで、いったん和の部分を無視したとき、 についての答えは と書けます。
和の部分が入るときのみ ではなく をかけることを考えると、 についての答えは と書けます。
これを変形すると となります。 とすると、 についての答えは と書けます。
ここで、 ともに次数が小さいものからマージするテクニックで で求めることができます。
よって、この問題を で解くことができました。