P7930 [COCI 2021/2022 #1] Set

In the well-known game SET, there are cards with different numbers, shapes, colors, and so on. The player’s goal is to find an existing triplet of cards (a triple of cards, i.e., a combination of three cards) that satisfies certain rules. Marin and Josip quickly got bored with this game and made it harder.

In this problem, each card is defined as a length $k$ sequence consisting only of $1, 2, 3$. There are $n$ cards. The cards are unordered, and it is guaranteed that the cards are **pairwise different**. We define a SET as an unordered triplet of cards such that, for every position, the three sequences are either all the same or all different. Using the original wording, this is “same” or “pairwise different”. More rigorously, let the three sequences be $S_i, S_j, S_k$. Then the following conditions must hold: * $i \lt j \lt k$. * $\forall x \in \left[1, k\right]$, we have $S_i(x) = S_j(x) = S_k(x)$ or $S_i(x) \neq S_j(x) \neq S_k(x)$. For example, $(1123, 1322, 1221)$ satisfies the rule: positions $1, 3$ are the same, and positions $2, 4$ are all different. Given these sequences, find how many essentially different SETs can be formed.

The first line contains two positive integers $n, k$. The next $n$ lines each contain a length $k$ sequence consisting only of $1, 2, 3$, representing a card. It is guaranteed that the sequences on the cards are all different.

Output one integer in a single line, representing the number of essentially different SETs that can be formed.

**[Sample Explanation \#3]** The two SETs that can be formed are $(S_1, S_2, S_3)$ and $(S_1, S_4, S_5)$. **[Constraints]** For all testdata, $1\le k\le 12$, $1\le n\le 3^k$, all $S_i$ are different, and $1\le S_i(x) \le 3$. | Subtask | Special Constraints | Score | | :-----: | :-----------------: | :---: | | $1$ | $k\le 5$ | $10$ | | $2$ | $k\le 7$ | $30$ | | $3$ | No special constraints | $70$ | #### Notes **The total score for this problem is $110$ points.** This problem is translated from [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2022) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T4 Set。 Translated by ChatGPT 5