第 4 题 Set (`set`)

CSP-S 复赛模拟赛 24 · 时间限制 1.0 s · 空间限制 256 MB · 45 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 set.in，输出文件 set.out。

题目描述

在知名游戏 SET 中，存在着一些数字、形状、颜色等不同的卡片，玩家的目标是确定一个存在的 triplet of cards（即卡片的三元组，也就是三张卡片构成的组合），使其符合特定的要求。Marin 和 Josip 很快就对这个游戏感到无趣，并对其进行了加强。

在本题中，定义每张卡片代表着一个仅由 $1, 2, 3$ 构成的长度为 $k$ 的序列，共有 $n$ 张卡片，卡片之间是无序的，保证卡片两两不同。

定义一个 SET 表示，当且仅当一个无序的 triplet of cards 其中的三个序列的每一位均相同或各不相同，用原文中的话就是 same 或 pairwise different，更严谨地表示，我们令这三个序列为 $S_i, S_j, S_k$ ，则一定满足如下条件：

$i < j < k$
$\forall x \in [1, k]$ ，满足 $S_i(x) = S_j(x) = S_k(x)$ 或 $S_i(x) \neq S_j(x) \neq S_k(x)$

例如 (1123, 1322, 1221) 便满足 1, 3 位均相同，2, 4 位各不相同。

给你这些序列，求可以组成多少种本质不同的 SET。

第一行为两个整数正整数 $n, k$ 。

接下来 $n$ 行中每一行包含一个仅由 $1, 2, 3$ 构成的长度为 $k$ 的序列，代表着一张卡片。

保证每张卡片上的序列不同。

仅一行一个整数，表示可以组成的本质不同的 SET 的数量。

输入：

输出：

输入：

2 2
11
22

输出：

输入：

输出：

【样例解释 #3】

可以组成的两个 SET 分别为 $(S_1, S_2, S_3)$ 和 $(S_1, S_4, S_5)$ 。

【数据范围】

对于全部数据， $1 \le k \le 12$ ， $1 \le n \le 3^k$ ， $S_i$ 互不相同， $1 \le S_i(x) \le 3$ 。

本题总分 110 分。

本题译自 Croatian Open Competition in Informatics 2021/2022 Contest #1 T4 Set。