ABC 180 F - Unbranched

• 問題
• AC

「最大サイズがちょうど$L$」の代わりに、$f(n, m, l) :=$連結成分のサイズが$l$を超えない$n$頂点$m$辺のグラフの数、を数えることにして、$f(N, M, L)-f(N, M, L-1)$を答えとすればよい。

次数2以下の連結成分はパスかサイクルしかないので、この2つを作りながら数えていくDPができそうだが、頂点の順番をどうするかが問題になる。順番を固定した上で最後に定数を掛けるのはうまくいかなそうだし、固定せずに挿入していくDPもサイズの上限に関する制約を扱うのが困難に見える。

こういう時の典型テクニックの一つとして、「選ぶ頂点の一つは、残っているものの中でもっとも小さい番号とする」というルールを追加してグループ（この場合は連結成分）を作っていくというものがある。この場合はこれがうまくいきそうだ。

$\operatorname{dp}[x][y] :=$頂点を$x$個、辺を$y$個使ってできる（条件を満たす）グラフの総数

とする。残った$N-x$個の頂点からサイズ$s$のパスグラフを作る時、連結成分のうちの1つの頂点は残った頂点の中でもっとも番号の小さいものと決めているので、残りは$N-x-1$個から$s-1$個を選ぶことになる。ラベル付きパスグラフの総数は$s!/2$（ただし$s=1$の場合は例外）なので、

$$\operatorname{dp}[x+s][x+s-1] \mathrel{{+}{=}} \frac{s!}{2} \binom{N-x-1}{s-1} \operatorname{dp}[x][y]$$

と遷移できる。サイクルを作る場合も同様で、ラベル付きサイクルグラフの総数は$(s-1)!/2$（ただし$s\le 2$の場合は例外）なので、

$$\operatorname{dp}[x+s][x+s-1] \mathrel{{+}{=}} \frac{(s-1)!}{2} \binom{N-x-1}{s-1} \operatorname{dp}[x][y]$$

と遷移する。ただし、自己ループである$s=1$は許されないことに注意。