#ABC485D. ABC|ABC|ABC
ABC|ABC|ABC
ABC|ABC|ABC
题目描述
给定一个长度为 的字符串 ,它只由 A、B、C 组成。
我们用两个位置把 切成三段非空的连续子串。形式化地,令 表示 的第 个字符;选择一对整数 ,满足 ,把 分成
$$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。
输入格式
输入第一行为一个整数 。
第二行为一个长度为 的字符串 。
输出格式
输出一行一个整数,表示满足条件的切法数。
12
AABCCABCCBCA
5
样例 1 解释
用 | 表示切开的位置,共有以下 种切法:
AABC|CAB|CCBCAAABC|CABC|CBCAAABC|CABCC|BCAAABCC|ABC|CBCAAABCC|ABCC|BCA
3
ABC
0
20
BCACABCACACABCAACBCA
65
数据范围
对于所有测试数据,保证:
- ;
- 是由
A、B、C组成、长度为 的字符串; - 为整数。
子任务
本题共 20 个测试点,按测试点计分:
| 测试点 | 分值 | 每个测试点 | 特殊性质 |
|---|---|---|---|
| 无特殊限制 |
每个测试点单独评分,全部测试点的得分之和即为本题得分。
相关
在下列比赛中: