好多牛牛

最优解

考虑动态规划 表示前个字符中，"niuniu"的前个字符选择的方案数。
那么对于第的位置来说，如果当前出现的是'n'，则可以更新"n"和"niun"的方案数，'i'可以更新'ni'和'niuni'的方案数，'u'可以更新'niu'和'niuniu'的方案数。
那么判断一下每个位置的字母并以此为依据转移即可。
时间复杂度
可以通过滚动数组将空间复杂度由降到
不加滚动数组优化版本：

int dp[100005][6]
int solve(string s){
    int mod = 1e9 + 7;
    for(int i = 1; i <= s.size(); ++i){
        for(int j = 0; j < 6; ++j) dp[i][j] = dp[i-1][j];
        if(s[i-1] == 'n'){
            dp[i][0] = (dp[i][0] + 1)%mod;
            dp[i][3] = (dp[i][3] + dp[i-1][2])%mod;
        }else if(s[i-1] == 'i'){
            dp[i][1] = (dp[i][1] + dp[i-1][0])%mod;
            dp[i][4] = (dp[i][4] + dp[i-1][3])%mod;
        }else if(s[i-1] == 'u'){
            dp[i][2] = (dp[i][2] + dp[i-1][1])%mod;
            dp[i][5] = (dp[i][5] + dp[i-1][4])%mod;
        }
    }return dp[s.size()][5];
}

加滚动数组优化的版本

int solve(string s){
    int dp[2][6]; memset(dp, 0, sizeof dp);
    int cur = 0, pre = 1;
    int mod = 1e9 + 7;
    for(int i = 0; i < s.size(); ++i){
        swap(cur, pre);
        for(int j = 0; j < 6; ++j) dp[cur][j] = dp[pre][j];
        if(s[i] == 'n'){
            dp[cur][0] = (dp[cur][0] + 1)%mod;
            dp[cur][3] = (dp[cur][3] + dp[pre][2])%mod;
        }else if(s[i] == 'i'){
            dp[cur][1] = (dp[cur][1] + dp[pre][0])%mod;
            dp[cur][4] = (dp[cur][4] + dp[pre][3])%mod;
        }else if(s[i] == 'u'){
            dp[cur][2] = (dp[cur][2] + dp[pre][1])%mod;
            dp[cur][5] = (dp[cur][5] + dp[pre][4])%mod;
        }
    }return dp[cur][5];
}