codeforces 1084C The Fair Nut and String dp

题目链接：

传送门

题意：
给出一个字符串，求由axxxxbxxxxa组成的字符串有多少种。

思路：

先将字符串处理一下，将连续的b和不是a和b的字符去除。

然后建立一个dp数组，其中dp[i]表示的是第1到i个字符可组成多少种符合题意的字符串。

if b[i]==\'b\'

     dp[i]=dp[i-1];

else 

     dp[i]=dp[i-1]+在i位置可以组成符合条件的字符串；

上述的字符串即为上一个字符\'b\'出现位置的dp值+1。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int ans=0;
typedef long long ll;
const ll mod=1e9+7;
ll dp[maxn];
char a[maxn];
char b[maxn];
int main()
{
    scanf(\"%s\",a);
    memset (dp,0,sizeof(dp));
    int len=strlen(a);
    int pos=0;
    for (int i=0;i<len;i++)
    {
        if(a[i]==\'a\')
            b[pos++]=a[i];
        else if(a[i]==\'b\'&&b[pos-1]!=\'b\')
            b[pos++]=a[i];
    }
    int last=0;
    for (int i=0;i<pos;i++)
    {
        if(b[i]==\'a\')
        {
            dp[i]=(dp[i-1]+last+1)%mod;
        }
        else
        {
            last=dp[i-1];
            dp[i]=dp[i-1];
        }
    }
    printf(\"%lld\\n\",dp[pos-1]%mod);
    return 0;
}