33OJ
登录 注册

#ABC485D. ABC|ABC|ABC

ABC|ABC|ABC

ABC|ABC|ABC

题目描述

给定一个长度为 NN 的字符串 SS,它只由 A、B、C 组成。

我们用两个位置把 SS 切成三段非空的连续子串。形式化地,令 SkS_k 表示 SS 的第 kk 个字符;选择一对整数 (i,j)(i,j),满足 1≤i<j<N1 \le i < j < N,把 SS 分成

$$S_1S_2\ldots S_i,\quad S_{i+1}S_{i+2}\ldots S_j,\quad S_{j+1}S_{j+2}\ldots S_N$$

三段。

求有多少种切法,使得这三段中的每一段都同时包含 A、B、C。

输入格式

输入第一行为一个整数 NN。

第二行为一个长度为 NN 的字符串 SS。

输出格式

输出一行一个整数,表示满足条件的切法数。

12
AABCCABCCBCA
5

样例 1 解释

用 | 表示切开的位置,共有以下 55 种切法:

  • AABC|CAB|CCBCA
  • AABC|CABC|CBCA
  • AABC|CABCC|BCA
  • AABCC|ABC|CBCA
  • AABCC|ABCC|BCA
3
ABC
0
20
BCACABCACACABCAACBCA
65

数据范围

对于所有测试数据,保证:

  • 3≤N≤3×1053 \le N \le 3 \times 10^5;
  • SS 是由 A、B、C 组成、长度为 NN 的字符串;
  • NN 为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 N≤2000N \le 2000
7∼207 \sim 20 7070 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。