P3501 [POI2010]ANT-Antisymmetry

定义一个01串是反对称子串当将原串取反后和原串一样。求串的反对称子串个数。\(|S|\leq 5\times 10^5\) 。

设 \(s[i],s[j]\) 是反对称子串中对应的字符

1.若子串长度为奇数，则存在 \(i=j\) 的一组情况，又 \(s[i]\) 取反 \(==s[j]\) 所以矛盾

2.子串长度为偶数， \(s[i]\) 取反 \(==s[j]\) ，所以对于一个长度偶数的串，对应位置上的数取反符合条件。将马拉车的代码修改一下即可。

#include<bits/stdc++.h>
using namespace std;

char s[1000005],ss[1000005];
int slen,mx,id,p[1000005];
long long ans;

int main()
{
	scanf("%d",&slen);
	scanf("%s",s+1);
	slen=strlen(s+1);
	ss[0]='*';ss[2*slen+1]='#';ss[2*slen+2]='!';
	for(int i=1;i<=slen;++i)
	{
		ss[2*i-1]='#';
		ss[2*i]=s[i];
	}
	slen=2*slen;
	for(int i=1;i<=slen;i+=2)
	{
		p[i]=i>mx?1:min(p[id*2-i],mx-i);
		while(ss[i-p[i]]+ss[i+p[i]]-'0'-'0'==1 || (ss[i-p[i]]==ss[i+p[i]] && ss[i-p[i]]=='#'))
			++p[i];
		if(i+p[i]>mx)
		{
			mx=i+p[i];
			id=i;
		}
		ans+=(p[i]-1)/2;
	}
	printf("%lld",ans);
	return 0;
}