AT_abc258_g [ABC258G] Triangle

题目描述

给定一个 $N$ 个顶点的简单无向图 $G$。

$G$ 通过 $N$ 行 $N$ 列的邻接矩阵 $A$ 给出。也就是说，当 $A_{i,j}$ 为 $1$ 时，表示顶点 $i$ 和 $j$ 之间有一条边；当 $A_{i,j}$ 为 $0$ 时，表示顶点 $i$ 和 $j$ 之间没有边。

请计算满足 $1 \le i < j < k \le N$ 的整数三元组 $(i, j, k)$ 的个数，使得顶点 $i$ 和 $j$ 之间、顶点 $j$ 和 $k$ 之间、顶点 $i$ 和 $k$ 之间都存在边。

输入格式

输入通过标准输入按以下格式给出。

$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

输入 #1

4
0011
0011
1101
1110

输出 #1

2

输入输出样例 #2

输入 #2

10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000

输出 #2

0

说明/提示

限制

• $3 \le N \le 3000$
• $A$ 是简单无向图 $G$ 的邻接矩阵。
• 输入均为整数。

样例解释 1

$(i, j, k) = (1, 3, 4), (2, 3, 4)$ 满足条件。$(i, j, k) = (1, 2, 3)$ 不满足条件，因为顶点 $1$ 和 $2$ 之间没有边。因此，答案为 $2$。

由 ChatGPT 4.1 翻译