刚学字符串，随便打打 Hash 基础题就打到了这道，然后阴差阳错入坑 Manacher 算法，再也回不过头了。这道题让你求反对称子串个数，就是在亦或意义下的回文子串，于是毅然决然选择了放弃在 \(O(n)\) 的马拉车（最后补回来了），所以两个做法都写写吧。
Hash
这道题让你求回文串的数量，考虑如何判定回文串。最基础的判断方法：预处理出 Hash 的前缀值和进制的次方，在查询的时候用 \(O(1)\) 的时间复杂度比较两个区间的哈希值是否相等，即可说明是否回文。一次比较的计算量为 \(O(1)\)，但是遍历整个字符串的所有子串需要 \(O(n^2)\) 的复杂度，相对失败。
如何优化？考虑使用科技“中心扩展法”。即把 \(S\) 的每个字符看作中心，然后左右扩展检查，判断它左右的对称位置是否相同，如果相同，那就是回文串的子串。如果不相同，那么停止判断。（这个尖端科技学了 Manacher 肯定是会的，因为 Manacher 就是对中心扩展法的优化）单纯扩展的复杂度为 \(O(n)\)，还是相对失败。注意到扩展时回文串的长度具有单调性（令 \(T\) 为 \(S\) 的子串且回文中心相等，如果 \(S\) 为回文串，那么 \(T\) 一定也是回文串），那么考虑使用二分法加速。
然后我们就明确了写题的方向，分为以下几步：
-
遍历 \(S\)，遍历到第 \(i\) 个的时候用二分法扩展左右两边，再使用哈希判断区间是否相等。
-
\(i\) 对答案的贡献即为回文串的左端点到中心的距离。
-
显然的性质：回文串长度一定为偶数。
所以写出代码（单哈希，自然溢出）
#include<bits/stdc++.h>
#define base 13331
using namespace std;
long long n;
char s[500005],fans[500005];
unsigned long long p[500005],sums[500005],sumfans[500005];
unsigned long long get_hash(int l,int r){
return sums[r]-sums[l-1]*p[r-l+1];
}
long long ans=0;
inline void binary_search(int x){
int l=0,r=min(n,n-x);
while(l<r){
int mid=(l+r+1)/2;
if(sums[x]-sums[x-mid]*p[mid]==sumfans[x+1]-sumfans[x+1+mid]*p[mid]){
l=mid;
}
else{
r=mid-1;
}
}
ans+=l;
}
int main(){
cin>>n;
scanf("%s",s+1);
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*base;
if(s[i]=='0'){
fans[i]='1';
}
else{
fans[i]='0';
}
}
for(int i=1;i<=n;i++){
sums[i]=sums[i-1]*base+(int)s[i];
}
for(int i=n;i>=1;i--){
sumfans[i]=sumfans[i+1]*base+(int)fans[i];
}
for(int i=1;i<n;i++){
binary_search(i);
}
cout<<ans<<endl;
}
然后呢，自己拿着 CF 上的卡哈希博客 造了一组，发现自己被卡了，然后往 OJ 里说了一声，然后开始改。改成了双底数哈希，过了 Hack。
#include<bits/stdc++.h>//ANT-Antisymmetry with base13331 + base131
#define int long long
#define base 13331
#define base2 131
#define mod 1000000007
using namespace std;
long long n;
char s[500005],fans[500005];
long long p[500005],p2[500005];
long long sums[500005],sumfans[500005],sums2[500005],sumfans2[500005];
long long step1,step2,step3,step4;
long long ans=0;
inline void binary_search(int x){
int l=0,r=min(x,n-x);
while(l<r){
int mid=(l+r)/2+1;
step1=(sums[x]%mod-sums[x-mid]%mod*p[mid]%mod+mod)%mod;
step2=(sumfans[x+1]%mod-sumfans[x+1+mid]%mod*p[mid]%mod+mod)%mod;
step3=(sums2[x]%mod-sums2[x-mid]%mod*p2[mid]%mod+mod)%mod;
step4=(sumfans2[x+1]%mod-sumfans2[x+1+mid]%mod*p2[mid]%mod+mod)%mod;
if(step1==step2&&step3==step4){
l=mid;
}
else{
r=mid-1;
}
}
ans+=l;
}
signed main(){
// freopen("Hack_testcase_input.in","r",stdin);
cin>>n;
scanf("%s",s+1);
p[0]=1,p2[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*base%mod;
p2[i]=p2[i-1]*base2%mod;
if(s[i]=='0'){
fans[i]='1';
}
else{
fans[i]='0';
}
}
for(int i=1;i<=n;i++){
sums[i]=sums[i-1]%mod*base%mod+s[i]%mod;
sums[i]%=mod;
sums2[i]=sums2[i-1]%mod*base2%mod+s[i]%mod;
sums2[i]%=mod;
}
for(int i=n;i>=1;i--){
sumfans[i]=sumfans[i+1]%mod*base%mod+fans[i]%mod;
sumfans[i]%=mod;
sumfans2[i]=sumfans2[i+1]%mod*base2%mod+fans[i]%mod;
sumfans2[i]%=mod;
}
for(int i=1;i<n;i++){
binary_search(i);
}
cout<<ans<<endl;
}
//11 10 00 01 10 01 11
//110 100 001 010 101 011
//1100 1001 0010 0101 1011
//11001 10010 00101 01011
//110010 100101 001011
//1100101 1001011
// 11001011
Manacher
原本不怎么会，吕明栩大佬跟我说了几句还是没懂，想了几下懂了。（2024.4.13 写的）
很巧妙的一点是这里需要定义一个数组，记录 \(S[i]\) 的反值，例如 \(1 \to 0\)，\(0\to 1\)，\(\$ \to \$\)。
lmx 还是强啊。挂一下他的代码（我自己的没调出来呢）
#include <bits/stdc++.h>//Manacher by lmx
#define int long long
using namespace std;
const int maxn=1500000;
char s[maxn],s1[maxn],dui[500];
int he,ge,n,you,dian,zhi[maxn];
signed main(){
cin>>n>>s1;
ge=2;
s[0]='Q';
s[1]='#';
for(int i=0;i<n;i++){
s[ge]=s1[i];
ge++;
s[ge]='#';
ge++;
}
dui['1']='0';
dui['0']='1';
dui['W']='W';
dui['Q']='Q';
dui['#']='#';
s[ge]='W';
for(int i=1;i<ge;i+=2){
if(you>i){
zhi[i]=min(zhi[dian*2-i],you-i);
}
else{
zhi[i]=1;
}
while(s[i+zhi[i]]==dui[s[i-zhi[i]]]){
zhi[i]++;
}
if(zhi[i]+i>you){
you=zhi[i]+i;
dian=i;
}
he=he+(zhi[i]-1)/2;
}
cout<<he<<endl;
return 0;
}
结束。
总结：很板子的 Manacher。但是我不会。还是菜啊。菜就多练，还有时间呢！
标签：int,POI2010,long,ANT,zhi,mod,500005,后面,回文 From： https://www.cnblogs.com/zxcqwq/p/18133491