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的子串
- 对于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 组数据,大概是你没有注意到逆元这个东西)
『源代码』
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~
1. 这里说的是平摊下来 ↩
2. 并不是真正的容斥原理,只是“全集-补集”而已 ↩