← 返回题目列表

AtCoder · abc348_f

I. 奇怪的相似

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

有 N 长度序列 M,表示为 A_1, A_2, \ldots, A_N。的 i第序列表示为 M 整数 A_{i,1}, A_{i,2}, \ldots, A_{i,M}.

两个序列 X 和 Y 长度 M 被认为是相似的当且仅当索引的数量 i (1 \leq i \leq M) 这样 X_i = Y_i 是奇数。

查找整数对的数量 (i,j) 满意 1 \leq i < j \leq N 这样 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