【题解】被诅咒的字符串

题意

给你一个串，已知串中的是由，是由，是由分裂来的。现在给你结果串，问你原串有多少种可能。

题解

考虑全是的串其原串有哪些可能呢。这个可能数其实一个斐波那契数列，从可以看出来，可以变为和，所以。也就是也就是斐波那契数列。那么结果就是每当遇到连续的一段或或时统计其个数，总的方案数=原方案数*，这里为斐波那契数列。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=1e5+5;
long long f[N];
int main()
{
    f[0]=1;
    f[1]=1,f[2]=2,f[3]=3;
    for(int i=4;i<= N; ++i)
    {
        f[i] = (f[i-1] +f[i - 2]) % mod;
    }
    int res=0;
    string s;
    cin>>s;
    long long ans=1;
    int V=0,D=0,C=0;
    for(int i=0; i<s.length(); ++i)
    {
        if(s[i] == 'W' || s[i] == 'B'||s[i]=='O')
        {
            printf("0\n");
            return 0;
        }
        if(s[i] == 'V')
        {
            V++;
        }
        else
            ans=(ans*f[V])%mod,V= 0;
        if(s[i] == 'D')
        {
            D++;
        }
        else
            ans=(ans*f[D])%mod,D=0;
        if(s[i] == 'C')
        {
            C++;
        }
        else
            ans=(ans*f[C])%mod,C=0;
    }
    ans=(ans*f[V])%mod;
    ans=(ans*f[D])%mod;
    ans=(ans*f[C])%mod;
    printf("%lld\n",ans);
    return 0;
}