F - Unbranched Editorial by maspy

O(N log N) 時間での解法

指数型母関数の基本的な扱いにより，\(O(N\log N)\) 時間で解くことができます．

問題のグラフは，各連結成分がパスまたはサイクルであるものです．

辺の個数が \(M\) という条件は，パスの個数が \(N-M\) であるという言い換えができます．

連結成分の大きさに関する条件は，次のように扱います．

  • すべての成分が \(L\) 以下である場合の数え上げから，すべての成分が \(L-1\) 以下である場合の数え上げを引く．

\(N-M\) を改めて \(k\) と書くなどすれば，結局，次が解ければよいです．

\(N\) 頂点ラベル付きグラフであって，連結成分が次のようになるものを数えよ．

  • \(L\) 頂点以下のパスであるような連結成分 \(k\) 個
  • \(L\) 頂点以下のサイクルであるような連結成分 \(0\) 個以上

以下，グラフはすべてラベル付きで数えます．また，単にパス・サイクルと言えば長さ \(L\) 以下のものを指すことにします．

指数型母関数とは，\(n\) 頂点の場合の数え上げが \(a_n\) 通りであるときの形式的べき級数 \(\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}\) のことをいいます．

次のような指数型母関数を考えます．

  • パスの指数型母関数 \(F_1\)
  • サイクルの指数型母関数 \(F_2\)
  • 連結成分が \(k\) 個のパスからなるグラフの指数型母関数 \(F_3\)
  • 連結成分が \(0\) 個以上のサイクルからなるグラフの指数型母関数 \(F_4\)
  • 連結成分が \(k\) 個のパスと \(0\) 個以上のサイクルからなるグラフの指数型母関数 \(F_5\)

\(F_1\), \(F_2\) の計算

\(n\) 頂点からなるパス・サイクルの個数を \(p_n\), \(c_n\) とすると次が成り立ちます．

  • \(n > L\) ならば \(p_n = c_n = 0\)．以下 \(n\leq L\) とする．
  • \(p_0 = 0\), \(p_1 = 1\)
  • \(n\geq 2\) に対して \(p_n = n!/2\) （パスに対して向きを定めると順列ができる）
  • \(c_0 = 0\)
  • \(c_1 = 0\) （本問ではループを認めていないため）
  • \(n\geq 2\) に対して \(c_n = p_{n-1}\) （ラベル最大の点を除くとパスができる）

\(F_3\) の計算

\(F_3 = \frac{F_1^k}{k!}\) です．これを確認します．

「\(k\) 個のパスを持つグラフ」の個数は「\(1, 2, \ldots, k\) というラベルのつけた \(k\) 個のパスを持つグラフ」の \(1/k!\) 倍であることはすぐに分かるので，後者を数えます．

パス \(1,2,\ldots,k\) の大きさ \(n_1,\ldots,n_k\) を決めたとき，\(n\) 頂点をこれらのパスに分ける方法の個数は，次の通りです： \(\frac{n!}{n_1!\cdots n_k!}\cdot p_{n_1}\cdots p_{n_k} = n!\cdot \frac{p_1}{n_1!}\cdots\frac{p_k}{n_k!}.\)

実際，\(n\) 頂点を成分に分ける方法を決めたあとで，それぞれの成分をパスにする方法を決めることを考えればよいです．よって，\(n\) 頂点をパス \(1,2,\ldots,k\) に分割する方法は

\(n!\sum_{n_1+\cdots+n_k=n}\frac{p_1}{n_1!}\cdots\frac{p_k}{n_k!} = n![x^n]F_1^k\)

となるので，\(F_3\) についても指数型母関数を考えていることを合わせて目的の式が得られます．

\(F_4\) の計算

連結成分の個数が \(k=0, 1, 2, \ldots\) 個の場合をすべて足すことで，

\(F_4 = \sum_{k=0}^{\infty}\frac{F_2^k}{k!} = \exp(F_2)\)

が分かります．指数型母関数の \(\exp\) を利用する最も基本的な状況でしょうか．

\(F_5\) の計算

\(F_5 = F_3F_4\) です．

\(n\) 頂点をパスに属する \(n_1\) 頂点とサイクルに属する \(n_2\) 頂点に分割したあと，それら \(n_1\) 頂点のグラフの定め方と \(n_2\) 頂点のグラフの定め方をかけることを考えると，\(c_n = \sum_{n_1+n_2=n}\frac{n!}{n_1!n_2!}a_{n_1}b_{n_2}\) というタイプの計算，したがって指数型母関数では単なる積になることが確かめられると思います．

解答例

なお，計算量オーダー \(O(N\log N)\) が可能ですが，上の提出は本問題の制約下では \(\Theta(NL)\) 時間で動作するアルゴリズムを使っています．

形式的べき級数の exp や pow はあまり定数倍がよくないので，\(N\) が小さい制約だと疎な形式的べき級数として扱う計算方法の方が実行速度で上回ります．本問題では \(\pmod{10^9+7}\) での計算であるからなおさらです．

疎な形式的べき級数の計算方法について： https://github.com/yosupo06/library-checker-problems/issues/767

posted:
last update: