AT_abc348_f [ABC348F] Oddly Similar

题目描述

有 $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$ 是“相似的”对数。

输入格式

输入以如下格式从标准输入读入。

$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}$

输出格式

请输出一个整数，表示满足条件的 $(i, j)$ 对的数量。

输入输出样例 #1

输入 #1

3 3
1 2 3
1 3 4
2 3 4

输出 #1

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

说明/提示

限制条件

• $1 \leq N \leq 2000$
• $1 \leq M \leq 2000$
• $1 \leq A_{i,j} \leq 999$
• 所有输入均为整数。

样例解释 1

$(i, j) = (1, 2)$ 满足条件。因为 $A_{1,k} = A_{2,k}$ 的 $k$ 只有 $k=1$ 这一个，因此个数为奇数。$(i, j) = (1, 3), (2, 3)$ 不满足条件，所以满足条件的 $(i, j)$ 只有 $(1, 2)$ 这一组。

由 ChatGPT 4.1 翻译