プレイヤー \(x\) と プレイヤー \(y\) の少なくとも一方が決勝に勝ちあがっているトーナメントの個数は次のように表せます。

\[c(x) + c(y) - c(x, y)\]

\(c(x)\) : プレイヤー \(x\) が決勝に進出しているトーナメントの個数

\(c(x, y)\) : プレイヤー \(x, y\) の両方が決勝に進出しているトーナメントの個数

これが \(M\) となるような組を数えたいです。

\(c(x, y) \geq 0\) であるため、\(c(x) + c(y) \geq M\) であり、\(\max(c(x), c(y)) \geq \frac{M}{2}\) が言えます。

ここで、\(\sum_{i=1}^{n} c(i) = 2M\) となるため、\(c(x) \geq \frac{M}{2}\) となるような \(x\) は、高々 \(4\) つしかありません。

よって、\(c(x) \geq c(y)\) となるような \(x\) を全列挙し、\(c(x,y)\) の計算にstd::mapを使うと、\(O(M + N\log M)\) でこの問題を解くことが出来ました。

実装例