BZOJ2084:[Poi2010]Antisymmetry hash+二分

思路:

貌似有\(O(n)\)的算法可是我根本懒得看.

只想出了\(O(nlogn)\)的二分+hash傻逼算法.

就是求一个原串的的01取反串的反串,把两个串接在一起,随后我们发现相同的串位置是关于中心对称的.

我们发现在对称轴确定时具有可二分性,于是\(O(n)\)枚举对称轴hash判断即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

#define N 500010
char s1[N],s2[N];

static const int base=2333;
static const int mod=233333333;
int mi[N],f1[N],f2[N];
int git1(int l,int r){return (f1[l]-(LL)f1[r+1]*mi[r-l+1]%mod+mod)%mod;}
int git2(int l,int r){return (f2[l]-(LL)f2[r+1]*mi[r-l+1]%mod+mod)%mod;}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
	#endif
	int n;scanf("%d",&n);
	scanf("%s",s1+1);register int i,j;for(i=1;i<=n;++i)s2[i]=s1[n-i+1]=='0'?'1':'0';
	//printf("%s\n%s\n",s1+1,s2+1);
	for(mi[0]=1,i=1;i<=n;++i)mi[i]=(LL)mi[i-1]*base%mod;
	for(i=n;i>=1;--i)f1[i]=((LL)base*f1[i+1]+s1[i])%mod;
	for(i=n;i>=1;--i)f2[i]=((LL)base*f2[i+1]+s2[i])%mod;

	long long res=0;
	int L,R,mid;
	for(i=1;i<=n;++i){
		j=n-i+1;
		L=0,R=min(i,n-i+1);
		while(L<R){
			mid=(L+R+1)>>1;
			if(git1(i-mid+1,i+mid-1)==git2(j-mid+1,j+mid-1))L=mid;else R=mid-1;
		}res+=L;
	}
	for(i=1;i<n;++i){
		j=n-i;
		L=0,R=min(i,n-i);
		while(L<R){
			mid=(L+R+1)>>1;
			if(git1(i-mid+1,i+mid)==git2(j-mid+1,j+mid))L=mid;else R=mid-1;
		}res+=L;
	}
	printf("%lld",res);
	return 0;
}