Constanze's Machine

原题地址
思路：

1. 因为字符串中不能有m，w的出现，所以有w,m的就全为零
2. 连续写几个u,或者m，发现连续的字符串符合斐波那切数列
3. 因为问的是最多有多少种“形态”，所以就是所有连续u，m的排列和之积

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mod =1000000007;
ll f[1000000];
void fi(){
    f[1]=1;f[2]=2;
    for(int i=3;i<=100000;i++){
        f[i]=f[i-1]+f[i-2];
        f[i]%=mod;
    }
}
char s[100000];
int main() {
   
    cin >>s;
    fi();
    //cout<<f[5]<<endl;
    ll sum=1,flagu=0,flagn=0,uu=0,nn=0;
    ll len = strlen(s);
    for(int i=0;i<len;i++){//cout<<"uu="<<f[uu]<<endl;cout<<"nn="<<f[nn]<<endl;cout<<"sum="<<sum<<endl;
        if(s[i]=='m'||s[i]=='w'){
             return cout<<0<<endl,0;
        }
        if(s[i]!='n'&&flagn) {sum*=f[nn];sum%=mod;nn=0;flagn=0;}
        if(s[i]!='u'&&flagu) {sum*=f[uu];sum%=mod;uu=0;flagu=0;}
        if(s[i]=='u'&&!flagu){
            flagu=1;
            uu++;
            continue;
        }
        if(flagu&&s[i]=='u') {uu++;continue;}
        //cout<<12346<<endl;

        if(s[i]=='n'&&!flagn){
            flagn=1;
            nn++;
            continue;
        }
        if(s[i]=='n'&&flagn) {nn++;continue;}
        //cout<<123<<endal;


    }
    sum%=mod;
    if(uu){
        sum*=f[uu];
    sum%=mod;
    }
    if(nn){sum*=f[nn];
    sum%=mod;}

    cout<<sum<<endl;
    return 0;
}