D - Another Racecar
Darjeeling
2
s
1024
MB
100
点
問題文
$N$ 個の文字列 $S _ 1,S _ 2,\ldots ,S _ N$ が与えられます。
$1$ 以上 $N$ 以下の整数のペア $(i,j)$ であって、 $S _ i$ と $S _ j$ をこの順に結合したものが回文であるようなものの個数を求めてください。
制約
- $N$ は整数で、 $2 \leq N \leq 400{,}000$
- $S _ i$ は英小文字からなる文字列
- $S _ i$ の長さは $1$ 以上 $400{,}000$ 以下である
- $S _ i$ ($1\leq i\leq N$) の長さの総和は $400{,}000$ 以下である
入力
$N$
$S _ 1$
$S _ 2$
$\vdots$
$S _ N$
出力
答えとなる整数を $1$ 行に出力してください。
入力例 1
5
race
car
rarer
re
racecar
出力例 1
3
- $S _ 1$ と $S _ 2$ をこの順に結合して得られる
racecarは回文です。 - $S _ 4$ と $S _ 3$ をこの順に結合して得られる
rerarerは回文です。 - $S _ 5$ と $S _ 5$ をこの順に結合して得られる
racecarracecarは回文です。
この他に、$S _ i$ と $S _ j$ をこの順に結合したものが回文となるようなペア $(i,j)$ はありません。
例えば、 $S _ 3$ と $S _ 4$ をこの順に結合して得られる rarerre は回文ではありません。
入力例 2
4
ab
aab
baa
aa
出力例 2
6
$(i,j)=(2,3),(2,4),(3,1),(3,2),(4,3),(4,4)$ のとき、結合した文字列が回文になります。