F - Oddly Similar

Contest Duration: 2024-04-06(Sat) 12:00 - 2024-04-06(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Oddly Similar Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $550$ 点

問題文

$N$ 個の長さ $M$ の数列 $A_1, A_2, \ldots, A_N$ があります。 $i$ 番目の数列は $M$ 個の整数 $A_{i,1}, A_{i,2}, \ldots, A_{i,M}$ で表されます。

それぞれの長さが $M$ の数列 $X,Y$ について、 $X_i = Y_i$ となるような $i(1 \leq i \leq M)$ の個数が奇数であるときに、 $X$ と $Y$ は似ていると言います。

$1 \leq i < j \leq N$ を満たす整数の組 $(i,j)$ のうち、 $A_i$ と $A_j$ が似ているものの個数を求めてください。

制約

$1 \leq N \leq 2000$
$1 \leq M \leq 2000$
$1 \leq A_{i,j} \leq 999$
入力は全て整数である。

入力

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

 $N$   $M$ 
 $A_{1,1}$   $A_{1,2}$   $\ldots$   $A_{1,M}$ 
 $A_{2,1}$   $A_{2,2}$   $\ldots$   $A_{2,M}$ 
 $\vdots$ 
 $A_{N,1}$   $A_{N,2}$   $\ldots$   $A_{N,M}$

出力

答えを整数として出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$(i,j) = (1,2)$ は条件を満たします。なぜならば、 $A_{1,k} = A_{2,k}$ となるような $k$ は $k=1$ の $1$ 個だけだからです。

$(i,j) = (1,3) ,(2,3)$ は条件を満たさないため、条件を満たす $(i,j)$ の組は $(1,2)$ だけです。

入力例 2Copy

Copy

6 5
8 27 27 10 24
27 8 2 4 5
15 27 26 17 24
27 27 27 27 27
27 7 22 11 27
19 27 27 27 27

出力例 2Copy

Copy

Score: $550$ points

Problem Statement

There are $N$ sequences of length $M$ , denoted as $A_1, A_2, \ldots, A_N$ . The $i$ -th sequence is represented by $M$ integers $A_{i,1}, A_{i,2}, \ldots, A_{i,M}$ .

Two sequences $X$ and $Y$ of length $M$ are said to be similar if and only if the number of indices $i (1 \leq i \leq M)$ such that $X_i = Y_i$ is odd.

Find the number of pairs of integers $(i,j)$ satisfying $1 \leq i < j \leq N$ such that $A_i$ and $A_j$ are similar.

Constraints

$1 \leq N \leq 2000$
$1 \leq M \leq 2000$
$1 \leq A_{i,j} \leq 999$
All input values are integers.

Input

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

 $N$   $M$ 
 $A_{1,1}$   $A_{1,2}$   $\ldots$   $A_{1,M}$ 
 $A_{2,1}$   $A_{2,2}$   $\ldots$   $A_{2,M}$ 
 $\vdots$ 
 $A_{N,1}$   $A_{N,2}$   $\ldots$   $A_{N,M}$

Output

Print the answer as an integer.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

The pair $(i,j) = (1,2)$ satisfies the condition because there is only one index $k$ such that $A_{1,k} = A_{2,k}$ , which is $k=1$ .

The pairs $(i,j) = (1,3), (2,3)$ do not satisfy the condition, making $(1,2)$ the only pair that does.

Sample Input 2Copy

Copy

6 5
8 27 27 10 24
27 8 2 4 5
15 27 26 17 24
27 27 27 27 27
27 7 22 11 27
19 27 27 27 27

Sample Output 2Copy

Copy