One-way and Once a Way

2 secs 1024 MB
riano_'s icon riano_

与えられた条件を言い換えると、「 NN 頂点の単純かつ連結なグラフであって、 11 から NN に至る一筆書きが存在するものの数」を求める問題となります。 このうち一筆書きに関する条件は、頂点 1,N1,N の次数(繋がっている辺の数)が奇数、その他の頂点の次数が偶数であることと同値です。

一旦、連結という条件を無視すると、 NN 頂点の完全グラフの全域部分グラフであって、指定した 22 点の次数が奇数であるものを数えることになりますが、この問題(を含む問題)はARCに出題例があります。

https://atcoder.jp/contests/arc115/tasks/arc115_d

以下、この問題は解けるものとして解説を進めますので、必要であれば上記問題の解説を参照してください。 また、以下の解説において上記ARCの問題の解法には触れませんが、計算量等は察しがついてしまうおそれが 00 ではありません。 完全な自力ACにこだわりたい方は念のため、以下を読まないことを推奨します。

上記問題を参照すると、 KK 頂点の単純な無向グラフであって、奇数次の頂点が LL 個指定されているもの(ただし、連結とは限らない)の数が求まりますので、これを f(K,L)f(K,L) とします。 ここで f(N,2)f(N,2) 通りある「連結とは限らないがその他の条件を満たすグラフ」から、頂点 1,N1,N を含む連結成分の大きさが N1N-1 以下であるものを取り除くことを考えます。 (奇数次の頂点はこの 22 つのみであるため、これらが同じ連結成分に属することは保証されます。) nn 頂点の場合の問題の答えを ans(n)ans(n) として、 s=2,...,N1s=2,...,N-1 までにおいて、問題の答え ans(s)ans(s) が求まっていると仮定し、帰納的に求めましょう。 すなわち、「連結とは限らないがその他の条件を満たすグラフ」の数 f(N,2)f(N,2) から、「頂点 1,N1,N を含む連結成分の大きさが ss であるもの」の数を、 s=2,...,N1s=2,...,N-1 まで順に引いていきます。

ある ss について、除くべきグラフの数は、「 1,N1,N 以外の s2s-2 頂点の選び方の数 N2Cs2_{N-2}C_{s-2} 」「選んだ ss 頂点内で完結する、連結かつ他の条件も満たすグラフの数 ans(s)ans(s) 」「残り NsN-s 頂点において、全ての頂点の次数が偶数であるようなグラフの数 f(Ns,0)f(N-s,0) (こちらは、連結である必要はありません)」の積によって求まります。 ここで、全ての頂点が偶数次となるグラフの数は、再び上記ARCの問題(の部分問題)に帰着するため上記の形で表せます。 まとめると、次の式になります。

  • ans(n)=f(n,2)s=2n1n2Cs2×ans(s)×f(ns,0)ans(n)=f(n,2)-\displaystyle\sum_{s=2}^{n-1} {}_{n-2}C_{s-2} \times ans(s)\times f(n-s,0)

以上のように、小さい数から順に求めていくことで O(N2log(N2))O(N^2log(N^2)) または、適切に前計算を行えば O(N2)O(N^2) で答えを求めることができました。