/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
0 か 1 で答える問題 M 問からなるテストがあり、これに 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 の正解した問題の数が等しい可能性がないようなものはいくつあるか求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq M \leq 20
- S_i は
0と1からなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 : S_N
出力
答えを出力せよ。
入力例 1
3 2 00 01 10
出力例 1
2
例えば 1 問目の正解と 2 問目の正解が共に 0 のとき、生徒 2 と生徒 3 の正解数は共に 1 となり等しくなります。一方、生徒 1 と生徒 2 のペア、生徒 1 と生徒 3 のペアでは、二人の正解数が等しいことはありません。
入力例 2
7 5 10101 00001 00110 11110 00100 11111 10000
出力例 2
10
Score : 300 points
Problem Statement
N students took a test with M questions with two choices: 0 and 1.
You are given N strings of length M each: S_1, S_2, \ldots, S_N.
The k-th character of S_i is 0 or 1, representing the response of the i-th student to the k-th question. Although we know the response of each student to each question, we do not yet know the correct answer ― 0 or 1 ― to each problem.
Find the number of pairs (i, j) satisfying 1 \leq i < j \leq N such that it is impossible for Student i and Student j to have the same number of correct answers.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq M \leq 20
- S_i is a string of length M consisting of
0and1.
Input
Input is given from Standard Input in the following format:
N M S_1 S_2 : S_N
Output
Print the answer.
Sample Input 1
3 2 00 01 10
Sample Output 1
2
For example, if the correct answers to the 1-st and 2-nd questions are both 0, Student 2 and Student 3 have the same number of correct answers ― 1. On the other hand, Student 1 and Student 2 never have the same number of correct answers, nor do Student 1 and Student 3.
Sample Input 2
7 5 10101 00001 00110 11110 00100 11111 10000
Sample Output 2
10