分数: 600 点
问题陈述
给你一个简单的无向图 G 与 N 顶点。
G 给出为 N \times N 邻接矩阵 A。也就是说,顶点之间有一条边 i 和 j if A_{i,j} is 1,并且没有 if A_{i,j} is 0.
求整数三元组的个数 (i,j,k) 满意 1 \le i < j < k \le N 使得顶点之间有一条边 i 和 j,顶点之间的边 j 和 k,以及顶点之间的边 i 和 k.
约束
- 3 \le N \le 3000
- A 是简单无向图的邻接矩阵 G.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}
输出
打印答案。
示例输入 1
4 0011 0011 1101 1110
示例输出 1
2
(i,j,k)=(1,3,4),(2,3,4) 满足条件。 仅
(i,j,k)=(1,2,3) 不满足条件,因为顶点之间没有边 1 和 2.
因此,答案是 2.
示例输入 2
10 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000
示例输出 2
0