AT_abc418_d [ABC418D] XNOR Operation

> 本题是 Problem G 的子问题。 一个由 `0` 和 `1` 组成的非空字符串 $S$，当且仅当满足以下条件时，被称为美丽字符串： - （条件）你可以重复执行以下操作，直到 $S$ 的长度变为 $1$，并且最终 $S$ 中唯一剩下的字符为 `1`。 1. 选择任意整数 $i$，满足 $1 \leq i \leq |S| - 1$。 2. 按如下方式定义整数 $x$： - 如果 $S_i = 0$ 且 $S_{i+1} = 0$，则 $x = 1$。 - 如果 $S_i = 0$ 且 $S_{i+1} = 1$，则 $x = 0$。 - 如果 $S_i = 1$ 且 $S_{i+1} = 0$，则 $x = 0$。 - 如果 $S_i = 1$ 且 $S_{i+1} = 1$，则 $x = 1$。 3. 移除 $S_i$ 和 $S_{i+1}$，并在它们的位置插入对应的数字 $x$。 例如，如果 $S = 10101$，选择 $i = 2$，操作后字符串变为 `1001`。 给定一个长度为 $N$ 的只包含 `0` 和 `1` 的字符串 $T$。 请你求出 $T$ 的子串中有多少个是美丽字符串。即使两个子串内容相同，只要它们取自不同的位置，也要分别计数。 什么是子串？一个字符串 $S$ 的**子串**是通过从 $S$ 的开头删除零个或多个字符，并从结尾删除零个或多个字符得到的字符串。 例如，`10` 是 `101` 的子串，但 `11` 不是 `101` 的子串。

输入按如下格式从标准输入给出： > $N$ $T$

输出 $T$ 的子串中美丽字符串的个数。

### 样例解释 1 通过取 $T$ 的第 1 到第 2 个字符得到的字符串 `11` 是美丽字符串，因为选择 $i = 1$ 并执行操作后，字符串变为 `1`。$T$ 的子串中美丽字符串有以下三个： - 取 $T$ 的第 1 个字符得到的字符串 `1`。 - 取 $T$ 的第 2 个字符得到的字符串 `1`。 - 取 $T$ 的第 1 到第 2 个字符得到的字符串 `11`。 ### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $N$ 是整数。 - $T$ 是长度为 $N$ 的、仅由 `0` 和 `1` 组成的字符串。 由 ChatGPT 4.1 翻译