STC02 - Antisymmetry

对于一个 01 字符串，如果将这个字符串 0 和 1 取反后，再将整个串反过来和原串一样，就称作「反对称」字符串。比如 00001111 和 010101 就是反对称的，而 1001 就不是。 现在给出一个长度为 n 的 01 字符串，求它有多少个子串是反对称的，注意这里相同的子串出现在不同的位置会被重复计算。 【输入格式】 第一行一个正整数 n 。 第二行一个长度为 n 的 01 字符串。 【输出格式】 一行一个整数，表示原串的反对称子串个数。 Translated by @xzjds

Byteasar studies certain strings of zeroes and ones. Let S be such a string. By S $ ^{r} $ we will denote the reversed (i.e., "read backwards") string S, and by S $ ^{I} $ we will denote the string obtained from S by changing all the zeroes to ones and ones to zeroes. Byteasar is interested in _antisymmetry_, while all things symmetric bore him. Antisymmetry however is not a mere lack of symmetry. We will say that a (nonempty) string S is _antisymmetric_ if, for every position i in S, the i-th last character is different than the i-th (first) character. In particular, a string S consisting of zeroes and ones is antisymmetric if and only if S=S $ ^{Ir} $ . For example, the strings 00001111 and 010101 are antisymmetric, while 1001 is not. In a given string consisting of zeroes and ones we would like to determine the number of contiguous nonempty antisymmetric fragments. Different fragments corresponding to the same substrings should be counted multiple times. Input ----- The first line of the standard input contains an integer N (1 <= N <= 500000) that denotes the length of the string. The second line gives a string of 0 and/or 1 of length N. There are no spaces in the string. Output ------ The first and only line of the standard output should contain a single integer, namely the number of contiguous (non empty) fragments of the given string that are antisymmetric. Example ------- For the input data: ``` 8 11001011 ``` the correct result is: `7`Antisymmetric fragments are: 01 (occurs twice), 10 (also twice), 0101, 1100, and 001011.