感觉智商莫名其妙的就变低了……写这题的时候死活想不出来……
做法其实不难……
题目要求形如ABA的串的个数，我们可以枚举A的长度，利用标记关键点的方法统计答案。设枚举到的答案为k，每k个点标记一个关键点，显然每个A只会恰好包含一个关键点，那么我们枚举每个关键点$i$，求一下它和$i+m+l$前后各能匹配到哪儿，显然答案应该加上能匹配的长度。注意为了防止重复计算需要把LCP和LCS(最长公共后缀)对$k$取min。
求LCP和LCS我是用hash写的，一开始base选的2147483647然后WA了，换成123456789和233333333倒是都能过……什么鬼……
1 /************************************************************** 2 Problem: 2119 3 User: hzoier 4 Language: C++ 5 Result: Accepted 6 Time:3664 ms 7 Memory:1800 kb 8 ****************************************************************/ 9 #include<cstdio> 10 #include<cstring> 11 #include<algorithm> 12 using namespace std; 13 const int maxn=50010; 14 const unsigned long long base=233333333ll; 15 unsigned long long gethash(int,int); 16 int LCP(int,int); 17 int LCS(int,int); 18 unsigned long long h[maxn],pw[maxn]; 19 long long ans=0; 20 int n,m,a[maxn]; 21 int main(){ 22 scanf("%d%d",&n,&m); 23 for(int i=0;i<n;i++)scanf("%d",&a[i]); 24 for(int i=n;i;i--)a[i]-=a[i-1]; 25 n--; 26 for(int i=n;i;i--)h[i]=h[i+1]*base+a[i]+base+1ull; 27 pw[0]=1; 28 for(int i=1;i<=n;i++)pw[i]=pw[i-1]*base; 29 for(int l=1;m+(l<<1)<=n;l++){ 30 for(int i=l;i+m+l<=n;i+=l){ 31 int tmpa=min(LCS(i,i+m+l),l),tmpb=min(LCP(i,i+m+l),l); 32 if(tmpa+tmpb>l)ans+=tmpa+tmpb-l; 33 } 34 } 35 printf("%lld",ans); 36 return 0; 37 } 38 inline unsigned long long gethash(int x,int l){return h[x]-h[x+l]*pw[l];} 39 int LCP(int x,int y){ 40 if(x>y)swap(x,y); 41 int L=1,R=n-y+1; 42 while(L<=R){ 43 int M=(L+R)>>1; 44 if(gethash(x,M)==gethash(y,M))L=M+1; 45 else R=M-1; 46 } 47 return R; 48 } 49 int LCS(int x,int y){ 50 if(x>y)swap(x,y); 51 int L=1,R=x; 52 while(L<=R){ 53 int M=(L+R)>>1; 54 if(gethash(x-M+1,M)==gethash(y-M+1,M))L=M+1; 55 else R=M-1; 56 } 57 return R; 58 }