【二分答案】【字符串哈希】bzoj2084 [Poi2010]Antisymmetry

显然只有偶数长度的串符合题意，并且如果一个串符合题意，那么从其首尾各截掉一个字符也符合题意。

于是枚举中心，二分可以向左右扩展的最远距离，累计答案。

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 500001

typedef unsigned long long ull;

const ull seed=3;

ull seeds[N],pre[N],rsuf[N],ans;

int n;

char s[N],s2[N];

ull Get(int l,int r){return pre[r]-pre[l-1]*seeds[r-l+1];}

ull Get2(int l,int r){return rsuf[l]-rsuf[r+1]*seeds[r-l+1];}

bool check(int x,int len){return Get(x-len+1,x+len)==Get2(x-len+1,x+len);}

void solve(int x)

{

	int l=0,r=min(x+1,n-x-1);

	while(r>l)

	  {

	  	int mid=(l+r+1>>1);

	  	if(check(x,mid)) l=mid;

	  	else r=mid-1;

	  }

	ans+=(ull)l;

}

int main()

{

	scanf("%d%s",&n,s);

	seeds[0]=1;

	for(int i=1;i<=n;++i) seeds[i]=seeds[i-1]*seed;

	for(int i=0;i<n;++i) pre[i]=pre[i-1]*seed+(s[i]-'0');

	for(int i=0;i<n;++i) s2[i]=(s[i]=='1'?'0':'1');

	for(int i=n-1;i>=0;--i) rsuf[i]=rsuf[i+1]*seed+(s2[i]-'0');

	for(int i=0;i<n-1;++i)

	  solve(i);

	cout<<ans<<endl;

	return 0;

}