果然还是要把manacher的一些经典题打一下。
求前K长的回文串（长度为奇数）的长度乘积。
如果有长度为7的回文串，就一定有长度1 3 5 的回文串。
一遍manacher把有的长度打上差分标记，最后快速幂计算即可。
#include<bits/stdc++.h> #define N 1000003 #define LL long long #define mod 19930726 using namespace std; int n,len,last; LL K; int pal[N<<1]; LL cha[N]; char s[N<<1],t[N]; void init() { len=strlen(t); s[0]='-'; for(int i=1;i<2*len;i+=2) { s[i]='#'; s[i+1]=t[i/2]; } s[2*len+1]='#'; s[2*len+2]='+'; s[2*len+3]=' '; last=len; len=2*len+1; } void manacher() { int id,mx=0; for(int i=1;i<=len;++i) { if(mx>=i)pal[i]=min(pal[2*id-i],mx-i+1); else pal[i]=1; while(s[i-pal[i]]==s[i+pal[i]])pal[i]++; if(i+pal[i]-1>mx)mx=i+pal[i]-1,id=i; if(s[i]!='#')cha[1]++,cha[pal[i]]--; } } LL quick(LL a,LL x) { LL ans=1; while(x) { if(x&1)ans=ans*a%mod; a=a*a%mod;x>>=1; } return ans; } int main() { scanf("%d%lld ",&n,&K); scanf("%s",t); init(); manacher(); for(int i=1;i<=last;i++) cha[i]+=cha[i-1]; int j=last; LL num=0; if(j%2==0)j--; LL ans=1; while(num<K&&j>0) { while(cha[j]<=0&&j>0)j-=2; if(j<=0)break; LL p=min(cha[j],K-num); num+=p; ans=ans*quick(j,p)%mod; j-=2; } if(num<K)printf("-1 "); else printf("%lld ",ans); } /* 3 3 aabbccbbaa 3 5 abc */
先处理出每个点最左和最优能被哪个回文中心覆盖到。
以向左为例：对于每个回文中心i，把mx到i+pal[i]-1打上i的标记。
向右同理。
枚举左回文串与右回文串的断点“#”，取长度相加的max。
#include<bits/stdc++.h> #define N 100003 #define LL long long #define mod 19930726 using namespace std; int n,len,last; LL K; int pal[N<<1],tl[N<<1],tr[N<<1]; LL cha[N]; char s[N<<1],t[N]; void init() { len=strlen(t); s[0]='-'; for(int i=1;i<len*2;i+=2) { s[i]='#'; s[i+1]=t[i/2]; } s[len*2+1]='#'; s[len*2+2]='+'; s[len*2+3]=' '; len=len*2+1; // for(int i=1;i<=len;++i)printf("%c",s[i]); printf(" "); } void manacher() { int id,mx=0; for(int i=1;i<=len;++i) { if(mx>=i)pal[i]=min(pal[2*id-i],mx-i+1); else pal[i]=1; while(s[i-pal[i]]==s[i+pal[i]])pal[i]++; if(i+pal[i]-1>mx)mx=i+pal[i]-1,id=i; } } int main() { scanf("%s",t); int n=strlen(t); init(); manacher(); int ml=1; for(int i=1;i<=len;++i) for(;ml<=i+pal[i]-1;++ml) tl[ml]=i;//存的回文中心的位置 int mr=len; for(int i=len;i>=1;--i) for(;mr>=i-pal[i]+1;--mr) tr[mr]=i; int ans=2; for(int i=1;i<n;i++)//枚举# ans=max(ans,tr[2*i+1]-tl[2*i+1]); //别忘了中间还有#号，tl和tr的位置相当于就是已经乘了2，所以算出来是双回文串的真实长度而不是一般 printf("%d ",ans); } /* baacaabbacabb aaaaaaaaaa */
求相交回文串对数。
正难则反。我们求不相交对数。
设L[i]为以i为开头的回文串个数。R[i]为以i为结尾的回文串个数。
有以i-pal[i]+1 ~ i-1开头的回文串个数，R同理。
打差分标记即可。
每次用总数减去不相交的即可。
#include<bits/stdc++.h> #define N 2000003 #define LL long long #define mod 51123987 using namespace std; int len,last; int pal[N<<1],l[N<<1],r[N<<1]; char s[N<<1],t[N]; LL quick(LL a,LL x) { LL res=1; while(x) { if(x&1)res=res*a%mod; a=a*a%mod;x>>=1; } return res; } void init() { s[0]='-'; for(int i=1;i<2*len;i+=2) { s[i]='#'; s[i+1]=t[i/2]; } s[2*len+1]='#'; s[2*len+2]='+'; s[2*len+3]=' '; len=2*len+1; } LL ans=0; void manacher() { int id,mx=0; for(int i=1;i<=len;++i) { if(mx>=i)pal[i]=min(pal[2*id-i],mx-i+1); else pal[i]=1; while(s[i+pal[i]]==s[i-pal[i]])pal[i]++; if(i+pal[i]-1>mx)mx=i+pal[i]-1,id=i; ans=(ans+(pal[i]>>1))%mod; l[i-pal[i]+1]++;l[i+1]--; r[i]++;r[i+pal[i]]--; } } int main() { scanf("%d",&len); scanf("%s",t); init(); manacher(); LL inv=quick((LL)2,(LL)mod-2); ans=(ans*(ans-1)/2)%mod; LL sum=0;//表示结尾为[1,i) for(int i=1;i<=len;++i) { l[i]+=l[i-1];r[i]+=r[i-1]; if(i&1)continue; ans=(ans-(sum*l[i]))%mod; ans=(ans+mod)%mod; sum=(sum+r[i])%mod; } printf("%lld ",ans); } /* */