[R34D]完美字符串 - 代码源竞赛平台

时空限制

1.5S/512M

题目描述

我们定义一个由 A、B、C 构成的字符串是完美的，当且仅当 A、B、C 三种字符出现的次数相等。

现在，给定一个整数 $n$ 与一个长度为 $3n$、仅由 A、B、C 构成的字符串 $S$。 你可以执行一次特殊操作：

• 选择一个非空区间 $[l, r]$ (其中 $1 \le l \le r \le 3n$) 与一个字符 $c \in \{$A, B, C$\}$，然后将字符串 $S$ 在区间 $[l, r]$ 内的所有字符全部修改为 $c$。

你的任务是，统计有多少个不同的三元组 $(l, r, c)$，使得在执行恰好一次上述操作后，得到的字符串 $S$ 是一个完美的字符串（即 A、B、C 各出现 $n$ 次）。

格式

输入格式

第一行包含一个正整数 $n$。

第二行包含一个长度为 $3n$ 的字符串 $S$。

输出格式

输出一个整数，表示满足条件的方案总数。

样例

样例输入 #1

2
AABBCC

样例输出 #1

9

样例输入 #2

2
ABCAAC

样例输出 #2

4

数据规模

对于 $40\%$ 的数据， $1\leq n \leq 1000$。

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$。字符串 $S$ 的长度为 $3n$，且仅由大写字母 A、B、C 构成。