Oddly Similar

题目描述

有 $N$ 个长度为 $M$ 的序列，记为 $A_1, A_2, \ldots, A_N$。第 $i$ 个序列由 $M$ 个整数 $A_{i,1}, A_{i,2}, \ldots, A_{i,M}$ 表示。 当且仅当满足等式 $X_i = Y_i$ 的索引数目 $i (1 \leq i \leq M)$ 为奇数时，长度为 $M$ 的两个序列 $X$ 和 $Y$ 被称为相似。 求满足 1 \leq i < j \leq N 且 $A_i$ 与 $A_j$ 相似的整数对 $(i,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}$

输出格式

输出一个整数，表示答案。

3 3
1 2 3
1 3 4
2 3 4

1

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

5

提示

$1 \leq N \leq 2000$ $1 \leq M \leq 2000$ $1 \leq A_{i,j} \leq 999$ 所有输入值均为整数。对于对 $(i,j) = (1,2)$ 满足条件，因为只有一个索引 $k$ 使得 $A_{1,k} = A_{2,k}$，即 $k=1$。 对 $(i,j) = (1,3), (2,3)$ 不满足条件，因此 $(1,2)$ 是唯一符合条件的一对。

标签: AtCoder|abc348F

来源

AtCoder|abc348F