← 返回题目列表

Codeforces · 1662/N

N. 无人机照片

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

今天,就像每年在 SWERC 一样,$$$n^2$$$ 参赛者聚集在会场外拍摄无人机照片。该活动的社交媒体经理 Jennifer 将它们排列成 $$$n\times n$$$ 的正方形。由于她非常擅长工作,她知道站在第 $$$i$$$ 行与第 $$$j$$$ 列交叉点的参赛者年龄为 $$$a_{i,j}$$$ 岁。巧合的是,她注意到没有两个参赛者年龄相同,每个人的年龄都在 $$$1$$$ 到 $$$n^2$$$ 岁之间。

Jennifer 计划让一些参赛者举起带有 ICPC 标志的横幅与地面平行,以便在航拍图片中清晰可见。为了拍摄完美的 SWERC 无人机照片,她将遵循以下步骤。

- 首先,Jennifer 将选择站在轴对齐矩形的顶点上的四名参赛者。
- 然后,她会让两名年轻参赛者握住其中一根杆子,而两名年长参赛者则握住另一根杆子。
- 最后,她将展开横幅,用杆子支撑其两端。显然,只有当两个极点平行且不交叉时才能做到这一点,如下图所示。

由于犹豫不决,Jennifer想尝试所有可能的横幅安排,但她担心这可能会导致参赛者迟到。有多少种不同的方式来选择四位拿着杆的选手才能拍出完美的照片?如果至少一名参赛者被包含在一个选项中,但另一个选项中不包含,则两个选项被认为是不同的。

输入

第一行包含一个整数 $$$n$$$ ($$$2\le n \le 1500$$$)。

接下来的 $$$n$$$ 行描述了参赛者的年龄。具体来说,第 $$$i$$$ 行包含整数 $$$a_{i,1},a_{i,2},\ldots,a_{i,n}$$$ ($$$1\le a_{i,j}\le n^2$$$)。

如果 $$$i\neq k$$$ 或 $$$j\neq l$$$ 则保证 $$$a_{i,j}\neq a_{k,l}$$$。

输出

打印 Jennifer 选择四名拿着杆的参赛者的方法数。

示例

输入 #1

2
1 3
4 2

输出 #1

0

输入 #2

2
3 2
4 1

输出 #2

1

输入 #3

3
9 2 4
1 5 3
7 8 6

输出 #3

6

注意

在第一个样本中,有 $$$4$$$ 参赛者,排列如下。

选择四名参赛者的方式只有一种,其中一杆由$$$1$$$和$$$2$$$年龄的参赛者持有,另一杆由$$$3$$$和$$$4$$$年龄的参赛者持有。但随后,正如我们在图中看到的,两极交叉了。

由于没有有效的方法来选择四名参赛者,所以答案是 $$$0$$$。

在第二个样本中,$$$4$$$ 参赛者的排列如下。

再次,选择四名参赛者的方法只有一种,但这次两极不交叉。

因此,答案是$$$1$$$。

在第三个样本中,$$$9$$$ 参赛者的排列如下。

有$$$6$$$选择四名参赛者的方法,使两极不交叉,如下图所示。