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算法以 \(O(n)\) 的复杂度^[1]求出以每个位置为中心的最长的回文子串。但是根据题目意思，可以发现它是求的所有的回文子串（例如Manacher算法可以求出较长的回文子串"abba"，但题目要求的是同时求得 "abba","bb"），因此我们需要根据求出的较长回文子串推导出所有的回文子串：

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

对于len为奇数，则会有回文子串 \([lef,rig]、[lef+1,rig-1]、...、[mid,mid]\)；
对于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 组数据，大概是你没有注意到逆元这个东西）

『源代码』

/*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;

}

\(\mathcal{The\ End}\)

\(\mathcal{Thanks\ For\ Reading!}\)

(各位reader有什么不懂的在邮箱里面问嘛 - \(lucky\_glass@foxmail.com\))

这里说的是平摊下来 ↩︎
并不是真正的容斥原理，只是“全集-补集”而已 ↩︎

巴特西

竞赛题解 - Palisection(CF-17E)