Meta-set

题意翻译

### 题目翻译 你有一副牌，每张牌包含$k$个特征，每个特征等于集合 $\{0，1，2\}$ 中的一个值。显然，共有$3^k$ 不同的情况。 定义一个三张牌为好的，当且仅当：对于同一位上的特征，要么**相同**，要么**两两不同**。如果**三张牌**所有$k$对特征都是好的，则称为一个集合。 如果一组**五张牌**中有严格意义上的**一个以上**的集合，则称为元组。在给定的$n$个不同的牌中，有多少个元组？ ### 输入格式 输入的第一行包含两个整数 $n$ 和 $k$ $( 1\le n\le 10^3)$ $( 1 \le k \le 20）$,表示桌子上的牌的数量和牌的特征的数量。在接下来的$n$行中，将对牌进行描述。 描述卡片的每一行包含$k$个整数，表示卡片特征$\{0，1，2\}$。所有卡片都是**不同的**。 ### 输出格式 输出一个整数表示元组的数量。

题目描述

You like the card board game "Set". Each card contains $ k $ features, each of which is equal to a value from the set $ \{0, 1, 2\} $ . The deck contains all possible variants of cards, that is, there are $ 3^k $ different cards in total. A feature for three cards is called good if it is the same for these cards or pairwise distinct. Three cards are called a set if all $ k $ features are good for them. For example, the cards $ (0, 0, 0) $ , $ (0, 2, 1) $ , and $ (0, 1, 2) $ form a set, but the cards $ (0, 2, 2) $ , $ (2, 1, 2) $ , and $ (1, 2, 0) $ do not, as, for example, the last feature is not good. A group of five cards is called a meta-set, if there is strictly more than one set among them. How many meta-sets there are among given $ n $ distinct cards?

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le n \le 10^3 $ , $ 1 \le k \le 20 $ ) — the number of cards on a table and the number of card features. The description of the cards follows in the next $ n $ lines. Each line describing a card contains $ k $ integers $ c_{i, 1}, c_{i, 2}, \ldots, c_{i, k} $ ( $ 0 \le c_{i, j} \le 2 $ ) — card features. It is guaranteed that all cards are distinct.

输出格式

Output one integer — the number of meta-sets.

输入输出样例

输入样例 #1

8 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
1 0 0 0
2 2 0 0

输出样例 #1

1

输入样例 #2

7 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
0 2 0 0

输出样例 #2

3

输入样例 #3

9 2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

输出样例 #3

54

输入样例 #4

20 4
0 2 0 0
0 2 2 2
0 2 2 1
0 2 0 1
1 2 2 0
1 2 1 0
1 2 2 1
1 2 0 1
1 1 2 2
1 1 0 2
1 1 2 1
1 1 1 1
2 1 2 0
2 1 1 2
2 1 2 1
2 1 1 1
0 1 1 2
0 0 1 0
2 2 0 0
2 0 0 2

输出样例 #4

0

说明

Let's draw the cards indicating the first four features. The first feature will indicate the number of objects on a card: $ 1 $ , $ 2 $ , $ 3 $ . The second one is the color: red, green, purple. The third is the shape: oval, diamond, squiggle. The fourth is filling: open, striped, solid. You can see the first three tests below. For the first two tests, the meta-sets are highlighted. In the first test, the only meta-set is the five cards $ (0000,\ 0001,\ 0002,\ 0010,\ 0020) $ . The sets in it are the triples $ (0000,\ 0001,\ 0002) $ and $ (0000,\ 0010,\ 0020) $ . Also, a set is the triple $ (0100,\ 1000,\ 2200) $ which does not belong to any meta-set. In the second test, the following groups of five cards are meta-sets: $ (0000,\ 0001,\ 0002,\ 0010,\ 0020) $ , $ (0000,\ 0001,\ 0002,\ 0100,\ 0200) $ , $ (0000,\ 0010,\ 0020,\ 0100,\ 0200) $ . In there third test, there are $ 54 $ meta-sets. 

**题目大意：**

有一副牌，每张牌有 $ k $ 个特征，每个特征可以是集合 $\{0, 1, 2\}$ 中的任意一个值。因此，总共有 $ 3^k $ 种不同的牌。

如果三张牌的所有 $ k $ 个特征都满足：要么三张牌在该特征上相同，要么在该特征上两两不同，则这三张牌构成一个“集合”。

如果有五张牌中严格意义上包含两个以上的“集合”，则这五张牌构成一个“元组”。

现在给定 $ n $ 张不同的牌，需要计算这些牌中可以构成多少个“元组”。

**输入格式：**

第一行包含两个整数 $ n $ 和 $ k $ ，分别表示牌的数量和每张牌的特征数量，满足 $ 1 \le n \le 10^3 $ 和 $ 1 \le k \le 20 $ 。

接下来的 $ n $ 行，每行包含 $ k $ 个整数，表示一张牌的特征值，每个特征值属于集合 $\{0, 1, 2\}$ 。保证所有牌都是不同的。

**输出格式：**

输出一个整数，表示可以构成的“元组”的数量。

**输入输出样例：**

**输入样例 #1：**
```
8 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
1 0 0 0
2 2 0 0
```
**输出样例 #1：**
```
1
```

**输入样例 #2：**
```
7 4
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 0
0 0 2 0
0 1 0 0
0 2 0 0
```
**输出样例 #2：**
```
3
```

**输入样例 #3：**
```
9 2
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
```
**输出样例 #3：**
```
54
```

**输入样例 #4：**
```
20 4
0 2 0 0
0 2 2 2
0 2 2 1
0 2 0 1
1 2 2 0
1 2 1 0
1 2 2 1
1 2 0 1
1 1 2 2
1 1 0 2
1 1 2 1
1 1 1 1
2 1 2 0
2 1 1 2
2 1 2 1
2 1 1 1
0 1 1 2
0 0 1 0
2 2 0 0
2 0 0 2
```
**输出样例 #4：**
```
0
```**题目大意：** 有一副牌，每张牌有 $ k $ 个特征，每个特征可以是集合 $\{0, 1, 2\}$ 中的任意一个值。因此，总共有 $ 3^k $ 种不同的牌。 如果三张牌的所有 $ k $ 个特征都满足：要么三张牌在该特征上相同，要么在该特征上两两不同，则这三张牌构成一个“集合”。 如果有五张牌中严格意义上包含两个以上的“集合”，则这五张牌构成一个“元组”。 现在给定 $ n $ 张不同的牌，需要计算这些牌中可以构成多少个“元组”。 **输入格式：** 第一行包含两个整数 $ n $ 和 $ k $ ，分别表示牌的数量和每张牌的特征数量，满足 $ 1 \le n \le 10^3 $ 和 $ 1 \le k \le 20 $ 。 接下来的 $ n $ 行，每行包含 $ k $ 个整数，表示一张牌的特征值，每个特征值属于集合 $\{0, 1, 2\}$ 。保证所有牌都是不同的。 **输出格式：** 输出一个整数，表示可以构成的“元组”的数量。 **输入输出样例：** **输入样例 #1：** ``` 8 4 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 2 0 0 1 0 0 1 0 0 0 2 2 0 0 ``` **输出样例 #1：** ``` 1 ``` **输入样例 #2：** ``` 7 4 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 2 0 0 1 0 0 0 2 0 0 ``` **输出样例 #2：** ``` 3 ``` **输入样例 #3：** ``` 9 2 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2 ``` **输出样例 #3：** ``` 54 ``` **输入样例 #4：** ``` 20 4 0 2 0 0 0 2 2 2 0 2 2 1 0 2 0 1 1 2 2 0 1 2 1 0 1 2 2 1 1 2 0 1 1 1 2 2 1 1 0 2 1 1 2 1 1 1 1 1 2 1 2 0 2 1 1 2 2 1 2 1 2 1 1 1 0 1 1 2 0 0 1 0 2 2 0 0 2 0 0 2 ``` **输出样例 #4：** ``` 0 ```