[ABC258G] Triangle
题意翻译
给你一个简单的无向图，其中有 $N$ 个顶点。用一个 的 $N\times N$ 邻接矩阵 $A$ 来表示。如果 $A_{i,j}=1$ ,则表示 $i$ 到 $j$ 有边相连，如果 $A_{i,j}=0$ ,则表示 $i$ 到 $j$ 无边相连。
求三元组 $(i,j,k)$ 的个数，满足 $1\leq i < j < k\leq n$，且 $i$ 与 $j$ 有边相连，$i$ 与 $k$ 有边相连，$j$ 与 $k$ 有边相连。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc258/tasks/abc258_g
$ N $ 頂点単純無向グラフ $ G $ が与えられます。
$ G $ は $ N $ 行 $ N $ 列の隣接行列 $ A $ によって与えられます。つまり、$ A_{i,j} $ が $ 1 $ である場合は頂点 $ i,j $ 間に辺があることを、$ 0 $ である場合には辺がないことを意味します。
$ 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
4
0011
0011
1101
1110输出样例 #1
2输入样例 #2
10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000输出样例 #2
0说明
### 制約
- $ 3\ \le\ N\ \le\ 3000 $
- $ A $ は単純無向グラフ $ G $ の隣接行列である。
- 入力はすべて整数。
### Sample Explanation 1
$ (i,j,k)=(1,3,4),(2,3,4) $ が条件を満たします。 $ (i,j,k)=(1,2,3) $ は、頂点 $ 1,2 $ 間に辺がないため条件を満たしません。 よって、解は $ 2 $ です。