Little Bobby Tables loves playing with tables. More specifically, he has a collection of $$$m$$$-by-$$$m$$$ tables, where each cell is either empty or colored in.
For two tables $$$T_1$$$ and $$$T_2$$$, Bobby defines the composition of $$$T_1$$$ and $$$T_2$$$ (denoted $$$T_1 \circ T_2$$$) to be the grid obtained by replacing each colored-in cell in $$$T_1$$$ with a copy of $$$T_2$$$, and each blank cell with a $$$m$$$-by-$$$m$$$ blank grid.
Examples of grid composition.
Two tables $$$T_1$$$ and $$$T_2$$$ are called commutative if $$$T_1 \circ T_2 = T_2 \circ T_1$$$. For example, the two tables in the picture above are not commutative, but two empty tables would be commutative.
You are given Bobby's collection of $$$n$$$ tables $$$T_1, T_2, \ldots, T_n$$$. Count the number of pairs $$$1 \leq i \lt j \leq n$$$ where $$$T_i$$$ and $$$T_j$$$ are commutative.
The first line contains $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 5$$$).
The descriptions of Bobby's $$$n$$$ tables follow. Each table is described by $$$m$$$ lines of $$$m$$$ characters each. Each character is either . (denoting an empty cell), or X (denoting a colored-in cell).
Print the number of commutative pairs.
3 3X.X.X.X.XX.XX.XX..X.X.X.X.X
1
4 5XXXX.X...XXXXX.X...XXXXX.XXXXXX...XXXXXXX...XX...XXXXXXX...XXXXXXX....X....XXXXXX....X....X....XXXXX
0
4 1.XX.
6
The first test corresponds to the pictures in the statement. Tables $$$T_1$$$ and $$$T_2$$$ are not commutative as shown above, and neither are $$$T_2$$$ and $$$T_3$$$. But $$$T_1$$$ and $$$T_3$$$ are equal, so $$$T_1 \circ T_3 = T_3 \circ T_1$$$. In total we have one commutative pair.
| Bay Area Programming Contest 2025 |
|---|
| Finished |
