自动搬运

查看原文

来自洛谷，原作者为

	Limie **

搬运于2025-08-24 21:49:06，当前版本为作者最后更新于2024-08-08 13:19:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 里统计数量即可。

upd on 2025/6/14: 单哈希被卡了，改了个双哈希

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;
constexpr int mod1=998244353,mod2=1e9+7,P=131;
int n;
unordered_map<LL,int> mp;
int qmi(int a,int b,const int mod)
{
	int ans=1;
	while(b){
		if(b&1)ans=(LL)ans*a%mod;
		b>>=1,a=(LL)a*a%mod;
	}return ans;
}
signed 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 s1=0,t1=1,s2=0,t2=1;
		while(c--){
			cin>>ch;
			t1=t1*P%mod1;
			s1=(s1*P+ch)%mod1;
			t2=t2*P%mod2;
			s2=(s2*P+ch)%mod2;
		}
		s1=s1*qmi(t1-1,mod1-2,mod1)%mod1;
		s2=s2*qmi(t2-1,mod2-2,mod2)%mod2;
		ans+=mp[s1*mod2+s2]++;
	}cout<<ans*2+n;
}