思路: 思维

考虑字符串中每个 ABBA 对答案的贡献。

下标从 $0$ 开始。假设是 s[i, i+3] = "ABBA"，那么这个 ABBA 对于答案的贡献为：所有 $l <= i, r >= i+3$ 的字符串。

这样的字符串一共有 $(l+1) \times (n-r)$ 个。

题目内容

对于一个仅由字符 'A' 和 'B' 组成的字符串，它的「幸运值」定义为字符串中连续子串 "ABBA" 的出现次数。例如，"ABBA" 的幸运值为 $1$ ，"ABBAABBA" 的幸运值为 $2$ ，"ABBBA" 的幸运值为 $0$ 。

现在，给定一个这样的字符串，请你计算它的所有子串的幸运值之和。

字符串的长度不超过 $2 \times 10^5$ 。

输入包含一行，为一个仅由字符 'A' 和 'B' 构成的字符串。