P10089 Sol
CarroT1212
·
·
题解
这题的题号在我们学校信息队有着特殊的意义，所以前来写了一下。
回文，但是在加起来之后。
Manacher 死透了，那剩下能快速判回文的方法就是哈希了，即回文串的前后两半的正反哈希相同。正好我们惊喜地发现只要底数够大（>200），哈希结果就是可以相加的！看起来非常符合本题要求。
发现由于回文性质，奇数答案和偶数答案是分别可以二分的。考虑对于奇数和偶数分别二分答案 mid，现在问题就变为怎么判断存不存在相加后长度为 mid 的回文串。
钦定 mid 是偶数。首先在 A,B 中正着和反着求一遍所有长度为 \frac{mid}{2} 的子串的哈希值。设串 s 的正反哈希值分别为 h_s,h'_s。
然后如果存在合法回文串，A,B 中就分别需要存在两个相邻的长度均为 \frac{mid}{2} 的子串 a_1,a_2 和 b_1,b_2，满足 h_{a_1+b_1}=h'_{a_2+b_2}\implies h_{a_1}+h_{b_1}=h'_{a_2}+h'_{b_2}\implies h_{a_1}-h'_{a_2}=h'_{b_2}-h_{b_1}。
你发现 (a_1,a_2),(b_1,b_2) 都只有 O(n) 对，所以直接预处理出所有可能的 h_{a_1}-h'_{a_2} 和 h'_{b_2}-h_{b_1} 的结果然后扔进 map 看一下有没有相等的即可。
复杂度 $O(n\log^2 n)$。有点小卡常，开 `unordered_map` 会好点。注意哈希值相减的时候[不要变成负数](https://www.luogu.com.cn/record/150787038)。
```cpp
const ll J=1e18,N=1e5+7,B[2]={211,213},P=1e9+9;
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll pw[N][2],pv[N][2];
ll n,m,a[N],b[N],ans;
ll af[N][2],ab[N][2],bf[N][2],bb[N][2];
bool chk(ll len,ll c) {
unordered_map<ll,ll> mp;
for (ll i=1;i+len*2+c<=n+1;i++) {
ll ha[2],hb[2];
for (ll o=0;o<2;o++)
ha[o]=(af[i+len-1][o]+P-af[i-1][o]*pw[len][o]%P)%P,
hb[o]=(ab[i+len+c][o]+P-ab[i+len*2+c][o]*pw[len][o]%P)%P;
mp[(ha[0]+P-hb[0])%P*P+(ha[1]+P-hb[1])%P]=1;
}
for (ll i=1;i+len*2+c<=m+1;i++) {
ll ha[2],hb[2];
for (ll o=0;o<2;o++)
ha[o]=(bf[i+len-1][o]+P-bf[i-1][o]*pw[len][o]%P)%P,
hb[o]=(bb[i+len+c][o]+P-bb[i+len*2+c][o]*pw[len][o]%P)%P;
if (mp.count((hb[0]+P-ha[0])%P*P+(hb[1]+P-ha[1])%P)) return 1;
}
return 0;
}
void mian() {
for (ll o=0;o<2;o++) {
pw[0][o]=1;
for (ll i=1;i<N;i++) pw[i][o]=pw[i-1][o]*B[o]%P;
for (ll i=0;i<N;i++) pv[i][o]=qp(pw[i][o]);
}
scanf("%lld%lld",&n,&m);
for (ll i=1;i<=n;i++) scanf("%lld",&a[i]);
for (ll i=1;i<=m;i++) scanf("%lld",&b[i]);
for (ll o=0;o<2;o++) {
for (ll i=1;i<=n;i++) af[i][o]=(af[i-1][o]*B[o]+a[i])%P;
for (ll i=n;i;i--) ab[i][o]=(ab[i+1][o]*B[o]+a[i])%P;
for (ll i=1;i<=m;i++) bf[i][o]=(bf[i-1][o]*B[o]+b[i])%P;
for (ll i=m;i;i--) bb[i][o]=(bb[i+1][o]*B[o]+b[i])%P;
}
for (ll c=0;c<2;c++) {
ll l=0,r=min(n,m)/2,mid,res=0;
while (l<=r) {
mid=l+r>>1;
if (chk(mid,c)) res=mid,l=mid+1;
else r=mid-1;
}
ans=max(ans,res*2+c);
}
cout<<ans;
}
```