DivineJK’s diary

Z cjikf c evf'

ABC180F - Unbranchedを形式的冪級数を使って解く

形式的冪級数（FPS）でやる解法で解いたので、まとめてみます。

問題リンク↓

考察

グラフに課される条件のうち、最初の2つの条件

自己ループを持たない
すべての頂点の次数が $2$ 以下である

から、考えるべきグラフは直線グラフか頂点数2以上のサイクル（を集めたもの）です。そして、3つめの条件

各連結成分のサイズを並べたとき、その最大値がちょうど $L$ である

についてですが、典型知識として、最大値がちょうど $L$ のものの数え上げは、（最大値が $L$ 以下であるものの個数）-（最大値が $L-1$ 以下であるものの個数）を求めれば良いです。ここまでは公式解説の通りです。

条件を満たすグラフで、連結成分のサイズの最大値が $L$ 以下であるものについて考えます。まずは、各連結成分のサイズの振り分け方を決めます。サイズ $i(1\le i \le L)$ の直線グラフの個数を $x _ {i}$ 、サイズ $i(1\le i \le L)$ のサイクルの個数を $y _ {i}$ とおくと、頂点数と辺の数の条件から、

という関係があります。この2式を整理して、

としておきます。

次に、各連結成分の頂点に番号を振ることを考えましょう。サイズ $i$ の直線グラフの各頂点に与える番号を $i$ 個とってきます。これらを各頂点に並べる方法は、反転して同じになるものを考慮して $i\ge 2$ のとき $i!/2$ 通り、 $i = 1$ のとき $1$ 通り、 $i\le 0$ のとき $0$ 通りです。これを一般に $f _ {1}(i)$ とおきます。

サイクルについても同様に、 $i\ge 3$ のとき $(i-1)!/2$ 通り、 $i = 2$ のとき $1$ 通り、 $i\le 1$ のとき $0$ 通りです。これを一般に $f _ {2}(i)$ とおきます。

さらに、辺にラベルがついてないことから、同じ頂点数、同じタイプの連結成分は区別しません。これをふまえて、求める個数は

です。和の範囲は $x _ {i}, y _ {j}$ が先ほどの条件を満たすようにとります。

形式的冪級数を使う

さて、この和の中にある積の部分ですが、なにか見覚えがないでしょうか？そうですね、expの級数展開の項に出てくるやつですね。以下のものを考えます。

これの $X, Y$ の指数は、それぞれ条件より $N, N - M$ となります。そしてこれは、

の $X^{N}Y^{N-M}$ の項にあたります。それぞれの級数はまさにexpの形そのものなので、それを用いて整理すると、

というとてもすっきりした形になります。これの $X^{N}Y^{N-M}$ の項を求めたいのですが、変数が2つあると複雑なので、偏微分的な要領で $X$ を定数とみなして $Y^{N-M}$ の項を求めましょう。exp型なので、この場合は $Y$ で $N-M$ 回偏微分すれば良いです。結局、

の $X^{N}$ の項を求めればよいことになります。これを $L-1$ でも同様に行い、その結果を $L$ のときの結果から引けば答えが求められます。

$\bmod 10^{9} + 7$ ですが、 $N, M, L$ が小さいことと、形式的冪級数の逆数などが登場しないことから、FPSのライブラリを持ち出さずにexpの冪級数展開を用いて計算したりしても間に合います。