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 翻译