← 返回题目列表

AtCoder · abc258_g

G. 三角形

中文机器翻译题面 查看原题

分数: 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