问题 2315 --反对称 Antisymmetry

2315: 反对称 Antisymmetry★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 12  解决: 10
[提交][状态][命题人:]

题目描述

对于一个 0/10/1 字符串，如果将这个字符串 00 和 11 取反后，再将整个串反过来和原串一样，就称作「反对称」字符串。比如 0000111100001111 和 010101010101 就是反对称的，而 10011001 就不是。
现在给出一个长度为 nn 的 0/10/1 字符串，求它有多少个子串是反对称的，注意这里相同的子串出现在不同的位置会被重复计算。

输入

第一行一个正整数 nn 。
第二行一个长度为 nn 的 0/10/1 字符串。

输出

一行一个整数，表示原串的反对称子串个数。
样例输入
Copy
8
11001011
样例输出
Copy
7

提示

对于 100\%100% 的数据， 1\le n\le 500\ 0001≤n≤500 000 。

来源

 

[提交][状态]