CF1735D · Meta-set

• 难度：1700
• 标签：brute force、combinatorics、data structures、hashing、math
• 链接：https://codeforces.com/problemset/problem/1735/D
• 时间限制：4 seconds　内存限制：256 megabytes
• 出现位置：Day21-字符串综合-hash-二分-构造/选做

中文题意

你喜欢卡牌桌游 "Set"。每张卡有 $k$ 个特征，每个特征取自集合 $\{0, 1, 2\}$。整副牌包含所有可能的卡牌，即共有 $3^k$ 张不同的卡。

对于三张卡，若某个特征在它们上完全相同或两两不同，则称该特征是"好的"。若三张卡的全部 $k$ 个特征都是好的，则称它们构成一个 set。

例如卡 $(0, 0, 0)$、$(0, 2, 1)$、$(0, 1, 2)$ 构成一个 set，而卡 $(0, 2, 2)$、$(2, 1, 2)$、$(1, 2, 0)$ 不构成（例如最后一个特征就不是好的）。

若五张卡中含有严格多于一个 set，则称这五张卡为一个 meta-set。给定 $n$ 张互不相同的卡，问其中共有多少个 meta-set？

输入格式（中文）

第一行两个整数 $n$ 和 $k$（$1 \le n \le 10^3$，$1 \le k \le 20$），分别为桌上卡牌数与卡牌特征数。接下来 $n$ 行描述这些卡。

每行描述一张卡，含 $k$ 个整数 $c_{i, 1}, c_{i, 2}, \ldots, c_{i, k}$（$0 \le c_{i, j} \le 2$），即卡的各特征。保证所有卡互不相同。

输出格式（中文）

输出一个整数——meta-set 的数量。

样例

样例 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

样例 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

输出：

3

样例 3

输入：

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

输出：

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

输出：

0