← 返回题目列表

AtCoder · past19_g

G. 结合法

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

问题陈述

你被给予 N-by-N 矩阵 A。 中的元素 i第行和 j第列 A 表示为 A(i,j)。 恰好有一个元素 A is 0,以及其他每个 (N^2-1) 元素是介于 1 和 N.

替换唯一元素有多少种方法 0 in A 之间的整数 1 和 N,包含在内,使得结果 A 满足以下条件?

  • A(A(i,j),k)=A(i,A(j,k)) 对于所有人 1\leq i,j,k\leq N.

约束

  • 1\leq N \leq 300
  • 0\leq A(i,j)\leq N
  • 恰好出现了一次 0 in A(i,j)\ (1\leq i,j\leq N).
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

3
1 2 3
2 0 1
3 1 2

示例输出 1

1

自从 A(2,2) is 0,我们考虑用之间的每个整数替换它 1 和 3.

  • If A(2,2) 变为 1:不满足条件。 (i,j,k)=(2,2,3),我们有 A(A(i,j),k)=3 但是 A(i,A(j,k))=2.
  • If A(2,2) 变为 2:不满足条件。 (i,j,k)=(3,3,2),我们有 A(A(i,j),k)=2 但是 A(i,A(j,k))=3.
  • If A(2,2) 变为 3:满足条件。 A(A(i,j),k)=A(i,A(j,k)) 对于所有人 1\leq i,j,k\leq N.

因此,答案是 1.


示例输入 2

3
2 1 0
1 2 3
1 3 2

示例输出 2

0

示例输入 3

6
4 5 5 2 4 2
5 2 2 4 5 4
5 2 0 4 5 4
2 4 4 5 2 5
4 5 5 2 4 2
2 4 4 5 2 5

示例输出 3

2