[COCI2021-2022#1] Set
题目背景
在知名游戏 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 \lt j \lt k $
* $ \forall x \in \left[1, k\right] $,满足 $ 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 的数量。
输入输出样例
输入样例 #1
3 4
1123
1322
1221
输出样例 #1
1
输入样例 #2
2 2
11
22
输出样例 #2
0
输入样例 #3
5 3
111
222
333
123
132
输出样例 #3
2
说明
**【样例解释 \#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$。
| Subtask | 特殊限制 | 分数 |
| :-----: | :--------: | :--: |
| $1$ | $k\le 5$ | $10$ |
| $2$ | $k\le 7$ | $30$ |
| $3$ | 无特殊限制 | $70$ |
#### 说明
**本题总分 $110$ 分。**
本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2012) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T4 Set。