\(0\) で初期化したカウンタ変数を準備します。そして、\(N\) 本の棒を棒 \(1\) 、棒 \(2\) 、\(\ldots\) 、棒 \(N\) の順に見ていき、今までに見たどの棒とも同じでない棒を見るたびにカウンタの値を \(1\) 増やすことで、 棒の種類数、すなわち本問題の答えが最終的なカウンタの値として得られます。

ある棒 \(i\) を見たときに、それが今までに見た棒 \(1, 2, \ldots, i-1\) のどれとも同じでないことを判定するには、

（ \(\star\) ） 文字列 \(S_i\) が、\(S_1, S_2, \ldots, S_{i-1}\) およびそれらを前後反転した文字列たちのどれとも異なるか

を判定すれば良いです。 これら全ての文字列と愚直に比較するとアルゴリズム全体で \(\Omega(N\sum_{i = 1}^N|S_i|)\) 時間かかるため実行制限時間に間に合わせるのは絶望的ですが、これまでに既に見た棒の文字列およびそれを前後反転した文字列たちを平衡二分木で保持することで、上記（ \(\star\) ）の判定はその平衡二分木に文字列 \(S_i\) が含まれるかの判定として十分高速に行うことができ、 アルゴリズム全体で \(O((\log N) \cdot\sum_{i = 1}^N|S_i|)\) 時間で本問題を解くことができます。

以下に、 C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main(void)
{
  int n;
  cin >> n;
  
  int ans = 0; set<string> T; string s;
  for(int i = 1; i <= n; i++){
    cin >> s;
    if(T.count(s) == 0) ans++;
    T.insert(s);
    reverse(s.begin(), s.end());
    T.insert(s);
  }
  cout << ans << endl;
  
  return 0;
}