隣接行列 \(A\) の \(i\) 行目を \(2\) 進数として見たものを \(A_i\) と置きます。

ここで、\(1 \le i < j < k \le N\) を満たす整数の組 \((i,j,k)\) を数えるのではなく、\(1 \le i,j,k \le N\) かつ互いに相異なる整数の組 \((i,j,k)\) を数えることを考えます。

\(i,j\) を固定した場合、条件を満たす \(k\) の個数は \(A_{i,k}=A_{j,k}=1\) となる \(k\) の個数と等しいです。

そしてこれは \(A_i\ \mathrm{AND}\ A_j\) の立っている bit 数と等しいです。

よって、bitset で \(A_1,A_2,\dots,A_N\) を管理し、\(i,j\) を全探索し \(A_i\ \mathrm{AND}\ A_j\) の立っている bit 数を \(\mathrm{O}(N)\) (ただし定数倍に \(\frac{1}{64}\) ) で求めることにより、\(\mathrm{O}(N^3)\)(ただし定数倍に \(\frac{1}{64}\) ) でこの問題を解くことができました。

\(\frac{3000^3}{64}=421875000 \simeq 4 \times 10^8\) であり、\(i<j\) となる \(i,j\) のみを探索することによってさらに定数倍として \(\frac{1}{2}\) をつけられることもありこの解法は十分高速です。