ARC115-D Odd Degree 解説

問題リンク

解説

まず、$N'$ 頂点の木に対しての場合を考える。 次数が奇数になる頂点の集合を適当にとると、要素数を $x$ 個として、$x$ が奇数ならそのような部分グラフは $0$ 通り、偶数なら $1$ 通りとなる。

$N'=1$ のとき明らかに成り立ち、それ以外は、木の葉をひとつとってくると、それに接続する辺を残すかどうかは一意に定まる。この過程で $x$ の偶奇は変わらないから、再帰的に行うと部分グラフも一意に定められる。

よって、$N'$ 頂点の木で $K$ 個の奇数次の頂点をつくる誘導部分グラフは、$K$ が偶数のときのみ $\binom{N'}{K}$ 通りある。

次に、一般の連結なグラフについて考える。 適当な全域木をとって、それ以外の辺を使うかどうかを決定してみる。すると、奇数次の頂点とする集合からそれ以外の辺のぶんの偶奇を差し引いてもやはり集合の要素数の偶奇は変わらないので、残りの全域木の辺を選んでこれを実現する方法は前で述べた通りになる。 よって、$N'$ 頂点 $M'$ 辺の連結なグラフについて、$K$ 個の奇数次の頂点を作る誘導部分グラフは、$2^{M'-N'+1}\binom{N'}{K}$ 通りある。

与えられるのは単純グラフなので、連結成分ごとに分けてこの値を計算して畳み込むと答えが計算できる。計算量は、畳み込みを愚直にやると $O(N^2)$, NTT を使うと $O(N\log^2 N)$ になる。