OI题解 - Palisection(CF-17E) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - Palisection(CF-17E)

发表于 更新于 分类于 Valine：

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. 并不是真正的容斥原理，只是“全集-补集”而已 ↩