1. 前言

感觉我的做法很简单啊，怎么题解区没有人写？

2. 前置知识点

哈希判断回文，快速幂求乘法逆。

3. 做法

设串 $s$ 的长度为 $|s|$，哈希值为 $a$，串 $t$ 的长度为 $|t|$，哈希值为 $b$。

不妨设哈希 base 为 $p$。

很难不发现 $s$ 与 $t$ 拼接起来为回文的条件为 $a \times p^{|t|}+b=b \times p^{|s|}+a$（因为 $s$ 和 $t$ 都是回文串），所以有

那么只要哈希求出每个串的哈希值，再对每个串算出上面的值然后扔到 map 里统计数量即可。

Code

#include<bits/stdc++.h>
namespace Limie{
	#define x first
	#define y second
	using namespace std;
	typedef long long LL;
	typedef unsigned long long ULL;
	typedef pair<int,int> PII;
}using namespace Limie;
const int mod=1e9+7,P=13331;
int n;
unordered_map<int,int> mp;
int qmi(int a,int b=mod-2)
{
	int ans=1;
	while(b){
		if(b&1)ans=(LL)ans*a%mod;
		b>>=1,a=(LL)a*a%mod;
	}return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int i;LL ans=0;
	cin>>n;
	for(i=1;i<=n;i++){
		int c=0;char ch;
		cin>>c;
		LL s=0,t=1;
		while(c--){
			cin>>ch;
			t=t*P%mod;
			s=(s*P+ch)%mod;
		}
		s=s*qmi(t-1)%mod;
		ans+=mp[s]++;
	}
	cout<<ans*2+n;
}