\(O(N^{4})\) で解けます。

公式解説をまず見てください。

\(dp[n][i][j]:=\) \(n\) 頂点トーナメントグラフ \(G\) と頂点集合 \(A,B\) の組のうち、 \(A\) のサイズが \(i\) であり、頂点番号が小さい方から大きい方へ向けられた辺が \(j\) 本あるようなものの個数

としてましたが、以下のように変更します。

\(dp[n][i][j]:=\) \(n\) 頂点トーナメントグラフ \(G\) と頂点集合 \(A,B\) の組のうち、 \(A\) のサイズが \(i\) であり、\(A\) に含まれている頂点から \(B\) に含まれている頂点の辺のうち、頂点番号が小さい方から大きい方へ向けられた辺が \(j\) 本あるようなものの個数

この dp は状態 \(O(N^{4})\) 遷移 \(O(1)\) なので、全体で、 \(O(N^{4})\) で求めることができます。

\(dp[N][i][j]\) の状態で、辺がどっち向きか決まっていないのは \(\frac{i(i-1)+(N-i)(N-1-i)}{2}\) 本です。

よって、答えは以下のようになります。

\(\sum_{i}\sum_{j}dp[N][i][j]\dbinom{\frac{i(i-1)+(N-i)(N-1-i)}{2}}{M-j}\)

事前に二項係数を前計算することで、このパートは \(O(N^{3})\) で計算できます。

dp がボトルネックとなって、 \(O(N^{4})\) で答えが求まります。