NOMURA プログラミングコンテスト 2020　D - Urban Planning

NOMURAコンのDが難しかったので解説書いておこうと思います。

問題概要は省略します。

解説

まずUnionFindを使って最初から決まっている値についてマージしていきます。ここで重要なことですが出来上がったそれぞれの連結成分について、 $-1$ の頂点は最大で一つまでしか含まれません。なぜなら $n$ 個の頂点を連結にするためには最低 $n-1$ 個の辺が必要だからです。連結成分の数を $m$ とすると、 $(n - 1)^k$ 通りそれぞれについて $(n - m)$ の辺が必要なことがわかるので、まずこれを答えに足します。

ここからは $-1$ の頂点について考えていきます。各連結成分についてサイズと $-1$ の頂点を含むかどうかの情報を持った配列を作っておくと便利です。最初に閉路を作ってしまうかどうかを考えずに連結成分同士の間に辺を作る場合の数を計算して足し、最後に閉路が生まれる場合の数を計算して答えから引きます。

$-1$ の頂点を含む連結成分と他の連結成分の間に辺を作る場合の数は、相手の連結成分のサイズを $s$ として、 $s * (n - 1)^{k - 1}$ 通りです。これを $m * (m - 1)$ の組み合わせそれぞれについて計算し足し合わせます。

最後に閉路が生まれるパターンを計算し引いていきます。 $-1$ の頂点を含まない連結成分は閉路に含まれることはないのでこれは連結成分の配列から除外しておきます。そうすると連結成分は合計 $k$ 個となります。editorialにも書いてあるように $j$ 個の連結成分を選び各連結成分のサイズを $s_i$ と置くと、これらの連結成分を自由な順番でつないでできる閉路は $s_1 * s_2 * ‥･ * s_j * (j - 1)!$ 通りあります。よって