CODE FESTIVAL Elimination Tournament F Unicyclic Graph Counting
これは解説 Advent Calendar 2017 の 21日目の記事です。
問題概要
頂点にラベルのついた $N$ 頂点 $N$ 本の辺からなる単純連結無向グラフのうち頂点 $i$ の次数が $d_i$ であるものはいくつあるか？ modulo $10^{9}+7$ で求めよ．
考察
各頂点の次数が与えられたときの，なもりグラフの数を数え上げる問題なことがすぐに分かります． これは複雑なので，まずはなもりグラフではなくて木の数を数え上げることにしましょう．
$N (N \geq 2)$ 頂点の木と対応関係があるような数列として，Prüfer Sequence が存在します． 木から Prüfer Sequence へと変換するアルゴリズム(以下，単に変換アルゴリズムと呼ぶ)は以下の通りです．
- 頂点の数が $2$ 以下ならば処理を終了する．
- 葉であるような頂点のうち，最も番号が小さいような頂点 $v$ を選ぶ
- $v$ を木から取り除き，$v$ と隣接した頂点の番号を数列の末尾に追加する
- 1 へ戻る
このようにして得られる長さ $N-2$ の数列は $N^{N-2}$ 通りあり，先述したようにそのどれもが木と対応関係があります． さらに，どの頂点も数列に書き込まれる回数が 次数 - 1 になっています．
そこで，木を数え上げるのではなくこの Prüfer Sequence の数を数えてみることにします． ありうる列は $\frac{(N-2)!}{(d_{1} - 1)!(d_{2} - 1)! \ldots (d_{N}-1)!}$ 個あり，これがありうる木の個数です． 以上より，木を数え上げる問題は $O(N)$ で解くことができます．
さて，この変換アルゴリズムをなもりグラフに対して適用することを考えてみます． このとき，最終的に残るグラフは閉路からただ $1$ つ頂点が出ている(これを足と呼ぶことにします)ようなグラフか単純サイクルのどちらかになります． 単純サイクルになるときは $N$ 頂点の単純閉路であるような場合だけなので割愛します．
足があるようなグラフのとき，各頂点が数列に現れる回数は以下のようになります．
- 閉路に含まれない頂点：次数 - 1 回
- 閉路に含まれる頂点であって，足が出ていない頂点：次数 - 2 回
- 閉路に含まれる頂点であって，足が出ている頂点：次数 - 3 回
ここで，なもりグラフが $K$ 頂点からなる閉路を持っていることを仮定しておきます．問題文の制約より，$K \geq 3$ とします． このとき，変換アルゴリズムを適用して得られうる長さ $N-K-1$ の数列は，"木の部分に関しては" 1:1 の対応関係があるような数列となります． 閉路の部分に関しては，$\frac{(K-1)!}{2}$ 通りの並べ方があります．
以上のことから，以下のようなことを覚えておけばいいことが分かります．
- 閉路を構成する頂点の個数
- 足が出ている頂点をすでに選んだかどうか
$\mathrm{dp}(i,j,k)=$ 頂点 $i$ までのうち，$j$ 個の頂点が閉路を構成する頂点であり，足が出ている頂点が $k$ 回出現するような選び方それぞれについて，係数を適切にかけた値の和，とします．これを求めたあと，係数 $\frac{(j-1)!(N-j-1)!}{2}$ をかけた値が答えです．以上より，この問題を $O(N^{2})$ で解くことができました．
ソースコード
using System;
using System.Linq;
using System.Collections.Generic;
namespace Program {
public class Solver {
const long MOD = (long)1e9 + 7;
static long ModPow(long x, long k) {
long ret = 1;
for (; k > 0; k /= 2, x = x * x % MOD)
if (k % 2 == 1) ret = ret * x % MOD;
return ret;
}
static long Inverse(long x) { return ModPow(x, MOD - 2); }
static void Add(ref long x, long y) { x = (x + y) % MOD; }
static void Main() {
var n = int.Parse(Console.ReadLine());
var d = Console.ReadLine().Split().Select(int.Parse).ToArray();
var fact = new long[n + 1];
var ifact = new long[n + 1];
fact[0] = ifact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = fact[i - 1] * i % MOD;
ifact[i] = Inverse(fact[i]);
}
//cycle
if (d.All(x => x == 2)) {
Console.WriteLine(fact[n - 1] * Inverse(2) % MOD);
return;
}
var dp = new long[n + 5, 2];
dp[0, 0] = 1;
foreach (var x in d) {
var next = new long[n + 5, 2];
for (int i = 0; i <= n; i++)
for (int k = 0; k < 2; k++) {
Add(ref next[i, k], dp[i, k] * ifact[x - 1]);
if (x >= 2) Add(ref next[i + 1, k], dp[i, k] * ifact[x - 2]);
if (k == 0 && x >= 3) Add(ref next[i + 1, k + 1], dp[i, k] * ifact[x - 3]);
}
dp = next;
}
long ans = 0;
for (int i = 3; i < n; i++) {
var coef = fact[n - i - 1] * fact[i - 1] % MOD;
Add(ref ans, dp[i, 1] * coef);
}
Console.WriteLine(ans * Inverse(2) % MOD);
}
}
}
コメント
- DEGwerさんのpdfにもあったように「ある操作列と対応するようなもの」をDPで数え上げるのがポイント
- あとは適切に係数をかけてやるだけ
