この解説において、文字列 \(S\) の \(k\) 文字目を \(S(k)\) と書くことにします。

◆ \(S_i = S_j\) という条件の整理

まずは、\(1\leq i < j \leq N\) に対して \(S_i = S_j\) となるのがどういうときかを考えましょう。

文字列の等式 \(S_i = S_j\) が成り立つことは、任意の \(k\) に対して \(S_i(k) = S_j(k)\) が成り立つことと同値です。\(S_i\), \(S_j\) の \(k\) 文字目が \(S\) の何文字目にあたるかを調べると、次のようになります：

• \(1\leq k < i\) のとき：\(S_i(k) = S(k)\), \(S_j(k) = S(k)\) が成り立つ。
• \(i\leq k < j\) のとき：\(S_i(k) = S(k+1)\), \(S_j(k) = S(k)\) が成り立つ。
• \(j\leq k < N\) のとき：\(S_i(k) = S(k+1)\), \(S_j(k) = S(k+1)\) が成り立つ。

したがって、\(S_i=S_j \iff S(i) = S(i+1) = \cdots = S(j)\) であることが分かりました。

◆ 数え上げ

組 \((i,j)\) を数えますが、これを \(j\) ごとに場合分けして数えることとします。各 \(j\) に対して、次が計算できればよいです：

\(S(i) = \cdots = S(j)\) となる \(i<j\) の個数 \(n_j\) を求めよ。

まず、\(S(j-1)\neq S(j)\) ならば \(n_j = 0\) です。\(S(j-1)=S(j)\) ならば、この条件は 「\(i=j-1\) または、 \(i<j-1\) かつ \(S(i) = \cdots = S(j-1)\)」と書けるため、\(n_j = n_{j-1} + 1\) となります。

したがって、\(j=1, 2, \ldots\) の順に \(n_j\) を計算していけば、\(n_j\) はひとつあたり \(O(1)\) 時間で計算できます。以上により、本問題は \(O(N)\) 時間で解くことができます。

◆解答例

https://atcoder.jp/contests/arc130/submissions/27437636