题目描述

给出一个 $n\times n$ 的矩阵，问有多少对子矩阵有且仅有一个公共顶点，并且元素和相等。

请注意，这里的公共顶点是指顶点相交，而不是存在一个公共格子。请参考样例 1 来理解“公共顶点”的含义。

输入格式

输入的第一行包含正整数 $n$。

接下来 $n$ 行每行 $n$ 个整数，表示为 $a_{i,j}$，可能有负数。

输出格式

输出仅一行，符合条件的方案数。

3
1 2 3
2 3 4
3 4 8

7

4
-1 -1 -1 -1
1 2 3 4
1 2 3 4
1 2 3 4

10

5
-1 -1 -1 -1 -1
-2 -2 -2 -2 -2
-3 -3 -3 -3 -3
-4 -4 -4 -4 -4
-5 -5 -5 -5 -5

36

提示

数据范围

• 对于 $40\%$ 的数据，$1\le n\le 10$。
• 对于 $100\%$ 的数据，满足 $1\le n \le 50$，$- 1000\le a_{i,j}\le 1000$。

样例 1 解释

可能的矩形对如下：

$(0,0)-(1,1)$ 和 $(2,2)-(2,2)$；

$(1,0)-(1,0)$ 和 $(0,1)-(0,1)$；

$(2,0)-(2,0)$ 和 $(1,1)-(1,1)$；

$(1,1)-(1,1)$ 和 $(0,2)-(0,2)$；

$(2,1)-(2,1)$ 和 $(1,2)-(1,2)$；

$(2,0)-(2,1)$ 和 $(0,2)-(1,2)$；

$(1,0)-(2,0)$ 和 $(0,1)-(0,2)$。

共计 $7$ 对，所以输出 $7$ 。

说明

题目译自 COCI2013-2014 CONTEST #1 T3 RATAR。

$\mathtt{Subtask \ 0}$ 为样例数据。（10 pts）

$\mathtt{Subtask \ 1}$ 中所有的数据满足 $1\le n\le 10$。 （30 pts）

$\mathtt{Subtask \ 2}$ 中所有的数据满足 $1\le n \le 50$，$- 1000\le a_{i,j}\le 1000$。请注意本子任务的时限。（60 pts）