题解 P1117 【[NOI2016]优秀的拆分】

在收藏里躺了四个月的题（ 我们可以把问题转化为，求以 $i$ 开始的和以 $i$ 结尾的 $\texttt{AA}$ 串的个数，然后利用乘法原理可以求出答案 显然可以想到一个 $\mathcal O(n^2)$ 的哈希做法 然后你就得到了95分的好成绩 如何得到剩下的五分呢？ ~~套取数据~~ 我们可以考虑枚举 $\texttt{AA}$ 串的长度 $len$ 我们往字符串中的每个 $i\times len$ 标记为关键点，那么每个 $\texttt{A}$ 中肯定有一个关键点。 枚举相邻的两个关键点 $x,y$，求出他们的 $lcp$ 和 $lcs$ 因为 $lcp$ 和 $lcs$ 有一个点是重复的，所以如果 $lcp+lcs-1 <len$ 时，一定不存在跨过这个关键点的长度为 $len$ 的一个 $\texttt{A}$ 串 否则，对于 $i\in(x-lcs,x-lcs+1+(lcp+lcs-len)]$，一定存在以 $i$ 开头的 $\texttt{A}$ 长度为 $len$ 的 $\texttt{AA}$ 串，同理，对于末尾的一部分，我们也有以他们为结尾的满足条件的 $\texttt{AA}$ 串 这样的话，利用 SA 计算 lcp，lcs 的复杂度为 $\mathcal O(n\log n)$，枚举关键点的复杂度为调和级数 $\mathcal O(n\ln n)$，总复杂度为 $\mathcal O(n\log n)$ 代码还挺好写的小清新字符串题（ ```cpp #include <bits/stdc++.h> using namespace std; # define Rep(i,a,b) for(int i=a;i<=b;i++) # define _Rep(i,a,b) for(int i=a;i>=b;i--) # define RepG(i,u) for(int i=head[u];~i;i=e[i].next) typedef long long ll; const int N=3e4+5; template<typename T> void read(T &x){ x=0;int f=1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0'; x*=f; } int t,n; int l[N],r[N]; int box[N]; ll ans; struct Suffix_Array{ int m; char s[N]; int sa[N],rk[N],tp[N]; int height[N]; int st[N][17],lg[N]; void init(){ memset(sa,0,sizeof(sa)); memset(rk,0,sizeof(rk)); memset(height,0,sizeof(height)); memset(st,0x3f,sizeof(st)); } void RadixSort(){ Rep(i,1,m)box[i]=0; Rep(i,1,n)box[rk[i]]++; Rep(i,1,m)box[i]+=box[i-1]; _Rep(i,n,1)sa[box[rk[tp[i]]]--]=tp[i]; } void SA(){ m=26; Rep(i,1,n)rk[i]=s[i]-'a',tp[i]=i; RadixSort(); for(int k=1,t=0;t<n;k<<=1,m=t){ t=0; _Rep(i,n,n-k+1)tp[++t]=i; Rep(i,1,n)if(sa[i]>k)tp[++t]=sa[i]-k; RadixSort(); swap(rk,tp); rk[sa[1]]=t=1; Rep(i,2,n) rk[sa[i]]=tp[sa[i]]==tp[sa[i-1]]&&(sa[i]+k<=n&&sa[i-1]+k<=n&&tp[sa[i]+k]==tp[sa[i-1]+k])?t:++t; } Rep(i,1,n)rk[sa[i]]=i; int k=0; Rep(i,1,n){ if(rk[i]==1)continue; if(k)k--; int j=sa[rk[i]-1]; while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++; height[rk[i]]=k; } lg[1]=0; Rep(i,2,n)lg[i]=lg[i>>1]+1; _Rep(i,n,1){ st[i][0]=height[i]; Rep(j,1,16){ if(i+(1<<j-1)>n)break; st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]); } } } int LCP(int x,int y){ int l=rk[x],r=rk[y]; if(l>r)swap(l,r); l++; int k=lg[r-l+1]; return min(st[l][k],st[r-(1<<k)+1][k]); } }sa1,sa2; int main() { read(t); while(t--){ memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); sa1.init(),sa2.init(); ans=0; scanf("%s",sa1.s+1); n=strlen(sa1.s+1); Rep(i,1,n)sa2.s[n-i+1]=sa1.s[i]; sa1.SA(); sa2.SA(); Rep(len,1,n) for(int j=1;(j+1)*len<=n;j++){ int x=j*len,y=(j+1)*len; int lcp=sa1.LCP(x,y),lcs=sa2.LCP(n-x+1,n-y+1); lcp=min(lcp,len),lcs=min(lcs,len); if(lcp+lcs<=len)continue; l[y+lcp-(lcp+lcs-len)]++,l[y+lcp]--; r[x-lcs+1]++,r[x-lcs+1+(lcp+lcs-len)]--; } Rep(i,1,n)l[i]+=l[i-1],r[i]+=r[i-1]; Rep(i,1,n)ans+=1ll*l[i-1]*r[i]; printf("%lld\n",ans); } return 0; } ```