题面
https://www.luogu.org/problem/P3501
题解
#include<cstdio> #include<iostream> #include<cstring> #define ri register int #define N 500050 #define uLL unsigned long long using namespace std; int n; char s[N]; const uLL p=107; uLL sum1[N],sum2[N]; uLL pp[N]; uLL getv1(int l,int r) { return sum1[r]-sum1[l-1]*pp[r-l+1]; } uLL getv2(int l,int r){ return sum2[l]-sum2[r+1]*pp[r-l+1]; } int main(){ pp[0]=1; for (ri i=1;i<N;i++) pp[i]=pp[i-1]*p; scanf("%d",&n); scanf("%s",s+1); for (ri i=1;i<=n;i++) sum1[i]=sum1[i-1]*p+(s[i]-'0'); for (ri i=n;i>=1;i--) sum2[i]=sum2[i+1]*p+((s[i]-'0')^1); uLL ans=0; for (ri i=1;i<=n;i++) if (((s[i]-'0')^(s[i+1]-'0'))==1) { int lb=1,rb=min(i-1,n-i-1),ret=0; while (lb<=rb) { int mid=(lb+rb)/2; if (getv1(i-mid,i)==getv2(i+1,i+mid+1)) ret=mid,lb=mid+1; else rb=mid-1; } ans+=ret+1; } cout<<ans<<endl; }