(x,y)(1≤x<y≤N) の組を固定した場合にそれが条件を満たすかどうか判定することを考えます。
ai,j= -
のとき 2i の bit を立てた整数 bj、ai,j= o
のとき 2i の bit を立てた整数 cj を定義すると、問題文の条件は bx&cy,cx&by,cx&cy の全てが 0 であることと同値です(ただし、& は bit ごとの論理積を表します)。
bj,cj をそれぞれ std::bitset や多倍長整数で管理することでこの問題を解くことができます。計算量は O(wordsizeN3) です。