← 返回题目列表

Codeforces · 1735/D

D. 元集

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

你喜欢纸牌游戏“Set”。每张卡包含 $$$k$$$ 个特征,每个特征都等于集合 $$$\{0, 1, 2\}$$$ 中的一个值。这副牌包含所有可能的牌变体,即总共有 $$$3^k$$$ 种不同的牌。

如果三张牌的特征相同或成对不同,则该特征被称为良好。如果所有 $$$k$$$ 功能都适合三张卡,则将三张卡称为一组。

例如,卡片 $$$(0, 0, 0)$$$、$$$(0, 2, 1)$$$ 和 $$$(0, 1, 2)$$$ 构成一组,但卡片 $$$(0, 2, 2)$$$、$$$(2, 1, 2)$$$ 和 $$$(1, 2, 0)$$$ 不,例如,最后一个功能不好。

一组五张牌被称为元集,如果其中有严格多于一组的话。给定的 $$$n$$$ 不同卡中有多少个元集?

输入

输入的第一行包含两个整数 $$$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$$$) — 卡片特征。保证所有卡都是不同的。

输出

输出一个整数——元集的数量。

示例

输入 #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

注意

让我们抽出表示前四个特征的卡片。第一个功能将指示卡片上的对象数量:$$$1$$$、$$$2$$$、$$$3$$$。第二个是颜色:红、绿、紫。第三是形状:椭圆形、菱形、波浪形。第四是填充:开放式、条纹式、实心式。

您可以在下面看到前三个测试。对于前两个测试,元集被突出显示。

在第一个测试中,唯一的元集是五张牌 $$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$。其中的集合是三元组 $$$(0000,\ 0001,\ 0002)$$$ 和 $$$(0000,\ 0010,\ 0020)$$$。另外,集合是三元组 $$$(0100,\ 1000,\ 2200)$$$,不属于任何元集。

在第二个测试中,以下五张卡组是元集:$$$(0000,\ 0001,\ 0002,\ 0010,\ 0020)$$$, $$$(0000,\ 0001,\ 0002,\ 0100,\ 0200)$$$, $$$(0000,\ 0010,\ 0020,\ 0100,\ 0200)$$$。

在第三个测试中,有 $$$54$$$ 元集。