AT_abc310_c [ABC310C] Reversible

题目描述

有 $N$ 根插有若干球的棒，每个球上写有一个小写英文字母。

对于 $i = 1, 2, \ldots, N$，第 $i$ 根棒上插着的每个球上的小写字母由字符串 $S_i$ 表示。具体来说，第 $i$ 根棒上插着的球的数量等于字符串 $S_i$ 的长度 $|S_i|$，并且从棒的一端开始依次排列球上的字母，得到的字符串就是 $S_i$。

如果两根棒上插着的球上的字母，从任意一端开始依次排列后得到的序列相同，则认为这两根棒是相同的。更形式化地说，对于 $1 \leq i, j \leq N$，当且仅当 $S_i$ 与 $S_j$ 相同，或者 $S_i$ 与 $S_j$ 的反转字符串相同时，第 $i$ 根棒和第 $j$ 根棒被认为是相同的。

请输出 $N$ 根棒中有多少种不同的棒。

输入格式

输入按以下格式从标准输入给出。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

6
a
abc
de
cba
de
abc

输出 #1

3

说明/提示

限制条件

• $N$ 是整数
• $2 \leq N \leq 2 \times 10^5$
• $S_i$ 仅由小写英文字母组成
• $|S_i| \geq 1$
• $\sum_{i=1}^N |S_i| \leq 2 \times 10^5$

样例解释 1

• $S_2 = \texttt{abc}$ 与 $S_4 = \texttt{cba}$ 反转后相同，因此第 2 根棒和第 4 根棒被认为是相同的。
• $S_2 = \texttt{abc}$ 与 $S_6 = \texttt{abc}$ 完全相同，因此第 2 根棒和第 6 根棒被认为是相同的。
• $S_3 = \texttt{de}$ 与 $S_5 = \texttt{de}$ 完全相同，因此第 3 根棒和第 5 根棒被认为是相同的。 因此，6 根棒中有 3 种不同的棒，分别为第 1 根棒，第 2 根棒（与第 4、6 根棒相同），第 3 根棒（与第 5 根棒相同）。

由 ChatGPT 4.1 翻译