103485: [Atcoder]ABC348 F - Oddly Similar

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 1

3 3
1 2 3
1 3 4
2 3 4

Sample Output 1

1

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 2

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 2

5

问题描述

有$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)$的数量为奇数。

找出满足$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}$

输出

打印一个整数答案。

样例输入1

3 3
1 2 3
1 3 4
2 3 4

样例输出1

1

对$(i,j) = (1,2)$满足条件，因为只有一个索引$k$使得$A_{1,k} = A_{2,k}$，即$k=1$。

对$(i,j) = (1,3), (2,3)$不满足条件，因此$(1,2)$是唯一满足条件的对。

样例输入2

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

样例输出2

5