AT_abc485_d.ABC|ABC|ABC

普及-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a string SS of length NN consisting of A, B, and C.

We split SS at two positions to divide it into three non-empty substrings. Formally, let SkS_k denote the kk-th character of SS; we choose a pair of integers (i,j)(i, j) such that 1≤i<j<N1 \leq i < j < N, and divide SS into three substrings S1S2…SiS_1S_2 \ldots S_i, Si+1Si+2…SjS_{i + 1}S_{i + 2} \ldots S_j, and Sj+1Sj+2…SNS_{j + 1}S_{j + 2} \ldots S_N.

Find the number of ways to split SS such that each of the three substrings contains all of A, B, and C.

给你一个长度为 NN 的字符串 SS,其中只包含字符 A、B 和 C。

我们选择两个分割位置,将 SS 分成三个非空子串。形式化地说,记 SkS_k 为字符串 SS 的第 kk 个字符;我们选择一对整数 (i,j)(i, j),满足 1≤i<j<N1 \leq i < j < N,并将 SS 分割为以下三个子串:
S1S2…SiS_1S_2 \ldots S_i,
Si+1Si+2…SjS_{i + 1}S_{i + 2} \ldots S_j,
Sj+1Sj+2…SNS_{j + 1}S_{j + 2} \ldots S_N。

求满足每个子串均同时包含 A、B 和 C 的分割方式的总数。

输入格式

The input is given from Standard Input in the following format:

NN
SS

输入从标准输入中按以下格式给出:

NN
SS

输出格式

Print the answer.

输出答案。

输入输出样例

  • 输入#1

    12
    AABCCABCCBCA

    输出#1

    5
  • 输入#2

    3
    ABC

    输出#2

    0
  • 输入#3

    20
    BCACABCACACABCAACBCA

    输出#3

    65

说明/提示

Sample 1 Explanation:
Using | to denote the positions where the string is split, there are five ways to split it: AABC|CAB|CCBCA, AABC|CABC|CBCA, AABC|CABCC|BCA, AABCC|ABC|CBCA, and AABCC|ABCC|BCA.

Constraints

  • 3≤N≤3×1053 \leq N \leq 3 \times 10^5
  • NN is an integer.
  • SS is a string of length NN consisting of A, B, and C.

样例 1 解释:
用 | 表示字符串的分割位置,共有五种分割方式:AABC|CAB|CCBCA、AABC|CABC|CBCA、AABC|CABCC|BCA、AABCC|ABC|CBCA 和 AABCC|ABCC|BCA。

约束条件

  • 3≤N≤3×1053 \leq N \leq 3 \times 10^5
  • NN 是一个整数。
  • SS 是一个长度为 NN 的字符串,仅由字符 A、B 和 C 组成。

输入解题思路,AI测评打分。不知道怎么写?

首页