G - Associativity Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N 行 N 列の行列 A が与えられます。 A の i 行 j 列の要素を A(i,j) と表記します。 A の要素のうちちょうど 1 つが 0 で、それ以外の N^2-1 個は 1 以上 N 以下の整数です。

A の要素として唯一存在する 0 を 1 以上 N 以下の整数で置き換える方法であって、置き換えた後の A が以下の条件を満たすようなものの数を求めてください。

  • 全ての 1\leq i,j,k\leq N について、A(A(i,j),k)=A(i,A(j,k))

制約

  • 1\leq N \leq 300
  • 0\leq A(i,j)\leq N
  • A(i,j)\ (1\leq i,j\leq N) の中に 0 であるものはちょうど 1 つ存在する
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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) が 0 なので、これを 1 以上 3 以下の整数で置き換えたそれぞれの場合について条件を満たすか考えます。

  • A(2,2) を 1 で置き換えたとき：条件を満たしません。例えば、(i,j,k)=(2,2,3) のとき、A(A(i,j),k)=3 ですが A(i,A(j,k))=2 です。
  • A(2,2) を 2 で置き換えたとき：条件を満たしません。例えば、(i,j,k)=(3,3,2) のとき、A(A(i,j),k)=2 ですが A(i,A(j,k))=3 です。
  • A(2,2) を 3 で置き換えたとき：条件を満たします。全ての 1\leq i,j,k\leq N について、A(A(i,j),k)=A(i,A(j,k)) が成立します。

よって、答えは 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

Problem Statement

You are given an N-by-N matrix A. The element in the i-th row and j-th column of A is denoted by A(i,j). Exactly one element of A is 0, and each of the other (N^2-1) elements is an integer between 1 and N.

How many ways are there to replace the only element 0 in A with an integer between 1 and N, inclusive, such that the resulting A satisfies the following condition?

  • A(A(i,j),k)=A(i,A(j,k)) for all 1\leq i,j,k\leq N.

Constraints

  • 1\leq N \leq 300
  • 0\leq A(i,j)\leq N
  • There is exactly one occurrence of 0 in A(i,j)\ (1\leq i,j\leq N).
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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)

Output

Print the answer as an integer.

Sample Input 1

3
1 2 3
2 0 1
3 1 2

Sample Output 1

1

Since A(2,2) is 0, we consider replacing it with each integer between 1 and 3.

  • If A(2,2) becomes 1: it does not satisfy the condition. For (i,j,k)=(2,2,3), we have A(A(i,j),k)=3 but A(i,A(j,k))=2.
  • If A(2,2) becomes 2: it does not satisfy the condition. For (i,j,k)=(3,3,2), we have A(A(i,j),k)=2 but A(i,A(j,k))=3.
  • If A(2,2) becomes 3: it satisfies the condition. A(A(i,j),k)=A(i,A(j,k)) for all 1\leq i,j,k\leq N.

Thus, the answer is 1.

Sample Input 2

3
2 1 0
1 2 3
1 3 2

Sample Output 2

0

Sample Input 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

Sample Output 3

2