各 \(1 \leq M' \leq M\) について以下の問題を解くことができれば、元の問題に対する答えを計算することができます。

$N$ 頂点 $M'$ 辺無向単純グラフ全てに対して以下の条件を全て満たす順列 $P$ の個数の総和を求めよ。ただし、辺に番号はついていないものとする。

• 頂点 $i,j(i < j)$ 間に辺があるならば、$P_i > P_j$

まず、\(N \le M' +1\) という制約を付け加えたうえで解きます。 この場合は、\(\mathrm{DP}[i][j] = i\) 頂点 \(j\) 本グラフに対する解という動的計画法によって挿入 \(\mathrm{DP}\) をすると遷移を愚直に行っても \(\mathrm{O}(M^4)\) で解くことができます。

そして、次に連結グラフに対する場合の解を求めます。ここで、以下のような二変数形式的冪級数を考えます。

• \([x^Ny^M](N!)^2f(x,y)\) が \(N\) 頂点 \(M\) 辺グラフに対する解である形式的冪級数 \(f\)
• \([x^Ny^M](N!)^2g(x,y)\) が \(N\) 頂点 \(M\) 辺連結グラフに対する解である形式的冪級数 \(g\)

この時、\(f=\exp(g)\) が成り立つため、\(g=\log(f)\) となります。よって、\(g\) を \(\mathrm{O}(M^2\log M)\) で計算することができます。

次に、\([x^1y^0]g(x,y)=0\) と更新した場合の \(h=\exp(g)\) を考えます。

すると、\([x^Ny^M](N!)^2h(x,y)\) は \(N\) 頂点 \(M\) 辺グラフかつ、孤立点がないグラフに対する解となります。

この場合、\([x^Ny^M]h(x,y) \neq 0\) である \(N\) の範囲は \(N \le 2M\) であるため、\(N,M\) が与えられた場合、\(h\) の全ての項を全探索し、孤立点を追加することを考えることで \(\mathrm{O}(M^2)\) で解くことができます。

よってこの問題を解くことができました。計算量は \(\mathrm{O}(N+M^4+(T+\log M)M^2)\) です。