CF1084C.The Fair Nut and String

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

The Fair Nut found a string ss. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,…,pkp_1, p_2, \ldots, p_k, such that:

  1. For each ii (1≤i≤k1 \leq i \leq k), spi=s_{p_i} = 'a'.
  2. For each ii (1≤i<k1 \leq i \lt k), there is such jj that pi<j<pi+1p_i \lt j \lt p_{i + 1} and sj=s_j = 'b'.

The Nut is upset because he doesn't know how to find the number. Help him.

This number should be calculated modulo 109+710^9 + 7.

公平的坚果发现了一个字符串 ss。该字符串由小写拉丁字母组成。坚果是个充满好奇心的人,因此他想找出严格递增序列 p1,p2,…,pkp_1, p_2, \ldots, p_k 的数量,使得:

  1. 对每个 ii(1≤i≤k1 \leq i \leq k),有 spi=s_{p_i} = 'a';
  2. 对每个 ii(1≤i<k1 \leq i \lt k),存在某个 jj 满足 pi<j<pi+1p_i \lt j \lt p_{i + 1} 且 sj=s_j = 'b'。

坚果很沮丧,因为他不知道如何计算这个数量。请帮助他。

该数量需对 109+710^9 + 7 取模。

输入格式

The first line contains the string ss (1≤∣s∣≤1051 \leq |s| \leq 10^5) consisting of lowercase Latin letters.

第一行包含字符串 ss(1≤∣s∣≤1051 \leq |s| \leq 10^5),由小写拉丁字母组成。

输出格式

In a single line print the answer to the problem — the number of such sequences p1,p2,…,pkp_1, p_2, \ldots, p_k modulo 109+710^9 + 7.

在一行中输出该问题的答案——满足条件的序列 p1,p2,…,pkp_1, p_2, \ldots, p_k 的个数对 109+710^9 + 7 取模的结果。

输入输出样例

  • 输入#1

    abbaa

    输出#1

    5
  • 输入#2

    baaaa

    输出#2

    4
  • 输入#3

    agaa

    输出#3

    3

说明/提示

In the first example, there are 55 possible sequences. [1][1], [4][4], [5][5], [1,4][1, 4], [1,5][1, 5].

In the second example, there are 44 possible sequences. [2][2], [3][3], [4][4], [5][5].

In the third example, there are 33 possible sequences. [1][1], [3][3], [4][4].

在第一个例子中,有 55 种可能的序列:[1][1]、[4][4]、[5][5]、[1,4][1, 4]、[1,5][1, 5]。

在第二个例子中,有 44 种可能的序列:[2][2]、[3][3]、[4][4]、[5][5]。

在第三个例子中,有 33 种可能的序列:[1][1]、[3][3]、[4][4]。

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

首页