DP, 1d, fibonacci type
C. Constanze’s Machine
- personally i find this difficult to realize fibonacci base problem.
- you might want to see the tutorial for this problem.
Code
```cpp
void solve() {
string s;
cin >> s;
if (count(all(s), 'w') or count(all(s), 'm')) {
cout << 0 << '\n';
return;
}
vll dp(s.size() + 1, 0);
dp[0] = 1;
for (int i = 1; i <= s.length(); i++) {
if (i >= 2 and s[i - 1] == s[i - 2] and
(s[i - 1] == 'n' or s[i - 1] == 'u')) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1];
}
dp[i] %= mod;
}
cout << dp.back() << '\n';
}
```