题解 | #[POI2010]ANT-Antisymmetry#

一道板子题的小变式

思路：先观察反对称的定义--"对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串"
先确认一点，**长度为奇数的字符串一定不可能是反对称的，因为其0和1的个数不相等，在取反之后一定与原来的不同**

现在，探究一下反对称串的性质

设原字符串s长度为4，字符为s1,s2,s3,s4，对其取反，得到1-s1,1-s2,1-s3,1-s4，将其反过来会和原串一样
即有：s1=1-s4,s2=1-s3,s3=1-s2,s4=1-s1
可以发现，s1与s4相反，s2与s3相反
所以反对称的字符串就是一种特殊的回文串，只不过（左边）=（右边取反）
考虑manacher()算法，内部有一个 while(0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k]) k++;
发现，只需要把里面的==改成!=即可
最后统计所有偶数串的答案即可

tip:此题可以采用d1[],d2[]分开（即奇数串偶数串分开）的写法，个人认为更为便捷，因为这题只需要求出d2[]

代码如下

int d2[N]; 
//d2:以i为中心的长度为偶数的回文串个数
char s[N];
int n;
int cnt;

void manacher(){
	for(int i=0,l=0,r=-1;i<n;i++){
		int k=(i>r) ? 0 : min(d2[l+r-i+1],r-i+1);
		while(0<=i-k-1 && i+k<n && s[i-k-1]!=s[i+k]){ //板子，这里==改成!=就行
			k++;
		}
		d2[i]=k--;
		cnt+=d2[i]; //统计个数
		if(i+k>r){
			l=i-k-1;
			r=i+k;
		}
	}
	return ;
}

void InfiniteLight() {
	read(n);
	read(s);
	manacher();
	println(cnt);
	return ;
}