9分求条

#include<bits/stdc++.h>
using namespace std;
long long p[500010],qh1[500010],qh2[500010];
long long mod=1e9+7;
int ol=1313;
long long qj(int l,int r){
	return qh1[r]-qh1[l-1]*p[r-l+1]%mod;
}
long long qc(int l,int r){
	return qh2[r]-qh2[l-1]*p[r-l+1]%mod;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    p[0]=1;
    for (int i=1;i<=n;i++){
    	p[i]=p[i-1]*ol;
	}
	for (int i=1;i<=n;i++){
		qh1[i]=(qh1[i-1]*ol+(s[i]=='1'))%mod;
	}
	for (int i=1;i<=n;i++){
		qh2[i]=(qh2[i-1]*ol+(s[n-i+1]=='0'))%mod;
	}
	long long ans=0;
	for (int i=1;i<n;i++){
		int l=0,r=min(i,n-i);
		int maxx=0;
		while (l<=r){
			int mid=(l+r)/2;
			if (qj(i-mid+1,i+mid)==qc(n-i-mid+1,n-i+mid)){
				maxx=mid;
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		ans+=maxx;
	}
	cout << ans+1;
    return 0;
}
/*
1 2 3 4 5 6 7 8
i=3













*/