[POI2006] PAL-Palindromes 题解

· · 题解

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 都是回文串），所以有

\frac{a}{p^{|s|}-1}=\frac{b}{p^{|t|}-1}

那么只要哈希求出每个串的哈希值，再对每个串算出上面的值然后扔到 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;
}