\(\\\)
给定一个长度为\(N\)的小写字母串。问有多少对相交的回文子串\((\)包含也算相交\()\)，答案对\(51123987\)取模。
- \(N\in [1,2\times 10^6]\)
\(\\\)
\(Solution\)
先考虑相交如何处理。因为相交既跟端点有关，又跟长度有关，回文子串数目众多不好处理。正难则反。假设总回文串个数是\(cnt\)个，如果两两都相交一共有\(\frac{cnt\times(cnt-1)}{2}\)对，所以答案就是\(\frac{cnt\times(cnt-1)}{2}-\)不相交回文子串对数。
先考虑处理回文串个数回文串个数。在\(Manacher\)时可以直接求出，因为每一个长的回文串一定包含着若干个共同回文中心的回文子串，所以一个位置带来的回文串数就是这一位置的回文半径长度\((\)还原后\()\)。
在考虑处理不相交对数。统计以每一个位置为左端点和右端点的回文子串个数，根据端点处理。一个直接的想法是对每一个位置直接累加，右端点在它左边的子串数\(\times\)左端点在它右边的子串数，但这种方法显然会算重很多部分。考虑固定一侧，即确定左端点必须在这一位置，让这个子串数乘上右端点在它左边的子串数累加出来的答案，是不重不漏的，其中第二项做的时候可以前缀和处理。
关于以每一个开始和结束的回文子串数量，每求出一个位置暴力累加所有子串复杂度显然过不了。考虑差分。因为新加入的子串开头的位置一定是一段连续的区间，从最左的端点一直到回文中心，而结束的也是同理。最后对两个数列分别求一下前缀和就好，注意跟上一条结合在一起，右端点的数列会在计算过程中求两遍前缀和，即最后得到的是原数列的前缀和。
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #define N 2000010#define R register#define gc getchar#define mod 51123987using namespace std;typedef long long ll;char c,s[N<<1];ll ans;int n,p,mr,slen,l[N<<1],r[N<<1],len[N<<1];inline void init(){ scanf("%d",&n); while(!isalpha(c=gc())); s[1]=s[slen=3]='#'; s[2]=c; for(R int i=2;i<=n;++i){s[++slen]=gc();s[++slen]='#';} s[0]='['; s[slen+1]=']';}inline void manacher(){ for(R int i=1,p=0,mr=0;i<=slen;++i){ len[i]=(i>mr)?1:min(mr-i+1,len[(p<<1)-i]); while(s[i-len[i]]==s[i+len[i]]) ++len[i]; if(i+len[i]-1>mr){mr=i+len[i]-1;p=i;} ++l[i-len[i]+1]; --l[i+1]; ++r[i]; --r[i+len[i]]; (ans+=(ll)(len[i]>>1))%=mod; } ans=(ans*(ans-1)/2)%mod;}int main(){ init(); manacher(); for(R int i=1,sum=0;i<=slen;++i){ l[i]+=l[i-1]; r[i]+=r[i-1]; if(i%2==0){ ans=(ans-(ll)l[i]*sum%mod+mod)%mod; (sum+=r[i])%=mod; } } printf("%lld\n",ans); return 0;}