codeforces-1084C The Fair Nut and String(数学题)

发表于 | 更新于 | 阅读次数：

Problem is here

题意：

让你构造一个序列，有两个要求：1.全为’a’字符。2.每两个a字符之间一定夹着至少一个’b’字符，求能构造出多少个这样的序列

思路：

首先肯定是以b为切割点，计算出每段连续a序列的长度。对于一段长度为sum的’a’我们有sum+1种操作。因为可以不挑选这一段的’a’，在最后-1就是排除掉所有的’a’都不挑选的情况。那么解法就出来了：把每段a连续序列的长度加1再相乘，记得取模，最后输出时候，之前的积减去1，就是答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
using namespace std;
const int maxn=100001,mod=1000000007;
char s[maxn];
int b[maxn]={},n=0;
int main()
{
    scanf("%s",s);
    long long ans=1;
    for(int i=0 ; s[i]; i++)
    {
        if(s[i]=='a')
            b[n]++;
        else if(s[i]=='b'&&b[n])          
            n++;
    }
    for(int i=0 ;i<=n ;i++)
    {
        ans*=(b[i]+1);  
        ans%=mod;
    }
    printf("%lld\n",ans-1);

    return 0;
}
0%