本文共 1633 字，大约阅读时间需要 5 分钟。

$$ANT-Antisymmetry$$

题目链接： &

题目

对于一个$01$字符串，如果将这个字符串$0$和$1$取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如$00001111$和$010101$就是反对称的，$1001$就不是。

现在给出一个长度为$N$的$01$字符串，求它有多少个子串是反对称的。

输入

第一行，一个数字$N$，表示$01$字符串的长度。

输出

输出一个数字，就是所要求的答案。

样例输入

811001011

样例输出

7

样例解释

$7$个反对称子串分别是：$01$（出现两次），$10$（出现两次），$0101$，$1100$和$001011$

数据范围

$n\le 5\times 10^5$

思路

这道题可以用哈希$+$二分的方法来做。

代码

#include
   
    #define ll long long#define ull unsigned long long#define min(x, y) (x) < (y) ? (x) : (y)using namespace std;ll n, ans, p = 7 , P[500001], c[500001], d[500001];char a[500001], b[500001];ll work(ll i) {   //二分	ll l = 0, r = min(i + 1, n - i - 1);	while (l < r) {   		ll mid = (l + r + 1) >> 1;		if ((ull)(c[i] - c[i - mid] * P[mid]) == (ull)(d[i + 1] - d[i + 1 + mid] * P[mid])) l = mid;			else r = mid - 1;	}	return l;}int main() {   	scanf("%lld", &n);//读入	getchar();//处理换行符	scanf("%s", &a);//读入		for (ll i = 0; i < n; i++)//求出取反后的字符串		if (a[i] == '0') b[i] = '1';			else b[i] = '0';		P[0] = 1;//初始化	for (ll i = 1; i <= n; i++)//初始化		P[i] = P[i - 1] * p;		for (ll i = 0; i < n; i++)//求出未取反和取反的字符串的哈希值		c[i] = c[i - 1] * p + a[i] - 36;	for (ll i = n - 1; i >= 0; i--)		d[i] = d[i + 1] * p + b[i] - 36;		for (ll i = 0; i < n - 1; i++) {   //枚举反对称子串的中心		if (a[i] == a[i + 1]) continue;//没有反对称的		ans += work(i);//二分以此点为中心的反对称子串数量	}		printf("%lld", ans);//输出		return 0;}