トーナメントである有向グラフ \(G\) の強連結成分の個数は、以下の値 \(-1\) に等しいです。

• \(G\) の頂点集合 \(\lbrace 1,2,\dots,N \rbrace\) を \(2\) 個の頂点集合 \(A,B\) に分ける方法のうち、以下を満たすものの個数
  • \(A\) に含まれる頂点と \(B\) に含まれる頂点間にある辺は必ず \(A\) 側から \(B\) 側に貼られている。

これは、\(G\) の強連結成分を \(s_1,s_2,\dots,s_k\)(番号が小さい方が上流) とすると、\(0 \le i \le k\) を満たす整数 \(i\) に対する \(A=\lbrace s_1,s_2,\dots,s_i \rbrace,B=\lbrace s_{i+1},s_{i+2},\dots,s_k \rbrace\) の \(k+1\) 個が条件を満たすことから分かります。

さて、よって以下のような動的計画法を行うことが出来ます。

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

\(dp[n][i][j]\) からの更新は、以下のように行います。

• 頂点 \(n+1\) を \(A\) に追加するとき
  • \(A\) に含まれている頂点間との辺の向き付けは自由に行えます。
  • \(B\) に含まれている頂点間との辺は \(i+1\) から辺を向ける必要があります。
  • よって、\(0 \le k \le i\) に対して \(dp[n+1][i+1][j+k]\) に \(dp[n][i][j] \times \binom{i}{k}\) を加えます。
• 頂点 \(n+1\) を \(B\) に追加するとき
  • \(A\) に含まれている頂点間との辺は \(i+1\) へ辺を向ける必要があります。
  • \(B\) に含まれている頂点間との辺の向き付けは自由に行えます。
  • よって、\(0 \le k \le n-i\) に対して \(dp[n+1][i][j+i+k]\) に \(dp[n][i][j] \times \binom{n-i}{k}\) を加えます。

よって、状態数 \(\mathrm{O}(N^4)\) 遷移 \(\mathrm{O}(N)\) の動的計画法をすることで、\(\mathrm{O}(N^5)\) でこの問題を解くことが出来ます。また、定数倍が悪くなければ \(\mathrm{O}(N^5\log N)\)、\(\mathrm{O}(N^6)\) なども AC します。