OI题解 - Palisection(CF-17E)

Manacher学到一定程度,也需要练一下有趣的题了……
(这是多老的题了 $QwQ$)〔传送门〕


『题意』

给出一个字符串,求总共有多少对不同的(只要位置不同)回文子串有重叠。

举个例子(样例):”babb”
有 “bab”(0~2) , “b”(0) , “a”(1) , “b”(2) , “b”(3) , “bb”(2~3) 是回文子串,其中 (0~2) 与 (0),(1),(2),(2~3) 都有重叠,(2~3) 与 (2),(3) 有重叠,因此总共 6 对;

~(我希望我翻译得比较正确)~


『题解』

首先看到回文子串,我们可以用Manacher算法以 的复杂度1求出以每个位置为中心的最长的回文子串。但是根据题目意思,可以发现它是求的所有的回文子串(例如Manacher算法可以求出较长的回文子串”abba”,但题目要求的是同时求得 “abba”,”bb”),因此我们需要根据求出的较长回文子串推导出所有的回文子串:

令长度为 ,回文子串的左右端点分别为 ,中点 $mid=\left \lfloor \frac{lef+rig}{2} \right \rfloor$,定义 $[a,b] (a<b)$ 表示位置从a到b的子串

  1. 对于len为奇数,则会有回文子串 $[lef,rig]、[lef+1,rig-1]、…、[mid,mid]$;
  2. 对于len为偶数,则会有回文子串 $[lef,rig]、[lef+1,rig-1]、…、[mid,mid+1]$;

这样就可以把所有的回文子串都求出来了(而且恰好不重复)。

接下来就需要求有哪些相交……但是显然求相交的子串个数不如求不相交的子串个数——那么根据简单的“容斥”2,我们就可以求出答案。

(让我们先忽略题目中的“无序数对”,假设两个串的顺序是有影响的,即 A与B有重叠 ≠ B与A有重叠)
那么我们可以通过上面的方法求出总共有多少个回文子串,记为 $tot$,那么总共就有 $tot(tot-1)$ 对字符串。
然后计算有多少对是不重叠的。不重叠有两种情况:① 一个串的右端点在另一个串左端点的左边;②一个串的左端点在另一个串的右端点的右边
容易想到对于每个点,*存储以它结尾以及以它开始的回文子串的个数
,分别记为 ovr[],beg[]。那么我们就可以先从左到右扫描,得出结束位置小于当前位置的回文子串个数,再乘上以当前位置开始的回文子串的个数(组合数学的乘法原理)就是“右端点在左端点左边”的情况。反过来求“左端点在右端点右边”的情况也是一样的。

然后就剩下求 ovr[] 和 beg[] 的问题了。实际上在Manacher算法中每找到一个以当前位置为中心的最长回文子串$[lef,rig]$:
如果 $len$ 是奇数,则 ovr[mid~rig]++,beg[lef,mid]++;
如果 $len$ 是偶数,则 ovr[(mid+1)~rig]++,beg[lef,mid]++;

可见这是一个区间加和的问题……线段树?其实没有必要,可以直接用差分数组解决。

差不多就这样了,具体差分数组的实现以及其他的小细节留给reader们思考了~
(提示一下:如果你发现你WA在第 27 组数据,大概是你没有注意到逆元这个东西)


『源代码』

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZ=int(2e6);
const long long MOD=51123987ll,INV=(MOD+1)/2;
int len_str,len_mdy;
char str[SIZ+7],mdy[2*SIZ+7];
int haf[2*SIZ+7];
long long beg[SIZ+7],ovr[SIZ+7];
long long Manacher(){
int RIG=0,MID=0;
long long tot=0;
for(int i=1;i<len_mdy;i++){
if(i<RIG) haf[i]=min(haf[2*MID-i],RIG-i);
else haf[i]=1;
while(mdy[i-haf[i]]==mdy[i+haf[i]]) haf[i]++;
if(i+haf[i]>RIG) RIG=i+haf[i],MID=i;
int lef=(i-haf[i])/2,len=haf[i]-1,rig=lef+len-1,mid;
if(!len) continue;
if(len%2){ //01234 len=5
mid=lef+len/2;
ovr[mid]++;ovr[rig+1]--;
beg[lef]++;beg[mid+1]--;
tot+=len/2+1;
}
else{ //0123 len=4
mid=lef+len/2-1;
ovr[mid+1]++;ovr[rig+1]--;
beg[lef]++;beg[mid+1]--;
tot+=len/2;
}
tot%=MOD;
}
for(int i=0;i<len_str;i++){
beg[i]%=MOD;ovr[i]%=MOD;
ovr[i+1]+=ovr[i],beg[i+1]+=beg[i];
}
long long del=0,cnt=0;
for(int i=0;i<len_str;i++){
del=(del+beg[i]*cnt)%MOD;
cnt+=ovr[i];
cnt%=MOD;
}
cnt=0;
for(int i=len_str-1;i>=0;i--){
del=(del+ovr[i]*cnt)%MOD;
cnt+=beg[i];
cnt%=MOD;
}
tot=(tot+MOD-1)%MOD*tot%MOD;
tot=tot*INV%MOD;del=del*INV%MOD;
return (tot+MOD-del%MOD)%MOD;
}
int main(){
scanf("%d%s",&len_str,str);
len_mdy=len_str*2+2;
mdy[0]='+';mdy[1]='|';
for(int i=0;i<len_str;i++)
mdy[2*i+2]=str[i],mdy[2*i+3]='|';
long long res=Manacher();
printf("%lld\n",res);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

1. 这里说的是平摊下来
2. 并不是真正的容斥原理,只是“全集-补集”而已
0%