P6596 How Many of Them
まず除原理を用いて$ i頂点連結グラフの個数を求める。ここから$ i頂点二重辺連結グラフの個数を求める。方針としては橋を削除したときの連結成分を 1 個の頂点と見ていつもの字数制限付き木の数え上げを用いるが、素直に遷移を書くと 5 乗 log になってしまった。ただ定数倍がかなりつくであろうため書き終えると TLE したので何度も登場する項を前計算しておくことで mod を取る回数を減らして最悪ケースで AtCoder 上で 400 ms になったが、これでもまだ TLE したため埋め込んだ。
改めて考えると計算量が落ちることに気が付いた。dp の定義を $ dp_{i,j,k} = i個頂点を使って、二重辺連結成分が j 個あり、次数の合計が k であるときのスコアの総和と定義していた。ただし、スコアとは字数制限付き木の数え上げに必要する項やある二重辺連結成分から$ l本の橋が生えているとするとこの$ l本の辺をどの頂点から取るかの$ a^lなどの項などの総積とする。
ここで以下の問題を考える。
・$ N頂点の木を考える。頂点$ iの次数を$ d_iとした時木の得点は$ \prod_{i=1}^{N} a_i^{d_i}となる。全ての木に対する得点の総和を求めよ。
これは$ \prod_{i=1}^{N} a_i\exp(a_ix)の$ x^{N-2}の係数$ \times (N-2)!となるため k の情報は考える必要がなかった。よって計算量が 3 乗 log に落ちる。ここから母関数などを考えると計算量が更に落ちるかもしれないがとりあえず置いておく。