题目描述

有一个包含 $M$ 道只能用 $0$ 或 $1$ 回答的问题的测试，有 $N$ 名学生参加了该测试。给定 $N$ 个长度为 $M$ 的字符串 $S_1,S_2,\ldots,S_N$。$S_i$ 的第 $k$ 个字符是 0 或 1，表示第 $i$ 个学生对第 $k$ 道题的回答。每个学生对每道题的回答都是已知的，但每道题的正确答案到底是 $0$ 还是 $1$ 还未知。请你计算有多少对满足 $1\leq i<j\leq N$ 的 $(i,j)$，使得无论每道题的正确答案如何选择，学生 $i$ 和学生 $j$ 的正确题数都不可能相等。

输入格式

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

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出答案。

样例 1

输入

3 2
00
01
10

输出

2

样例 2

输入

7 5
10101
00001
00110
11110
00100
11111
10000

输出

10

说明/提示

限制条件

• $2\leq N\leq 10^5$
• $1\leq M\leq 20$
• $S_i$ 是由 0 和 1 组成的长度为 $M$ 的字符串

样例解释 1

例如，当第 $1$ 题和第 $2$ 题的正确答案都是 $0$ 时，学生 $2$ 和学生 $3$ 的正确题数都是 $1$，因此他们的正确题数可以相等。另一方面，对于学生 $1$ 和学生 $2$ 的组合、学生 $1$ 和学生 $3$ 的组合，无论如何选择每道题的正确答案，两人的正确题数都不会相等。

由 ChatGPT 4.1 翻译