B、tomorin的字符串迷茫值(状态机dp解法)

题目链接

逛了一圈发现还没有用状态机dp写的题解，这里发一个QAQ。

首先，很自然的一个状态定义是:

表示只考虑前 个字符，第 个字符不选（选）的所有方案中，子串 mygo 出现的次数。

我们的答案就是 + 。

考虑如何转移：

: 第 个不选，那么第 个字符一定要选，则 f[i][0] = f[i-1][1]。

: 第 个字符选的话，第 个字符可选可不选。

先算上前 个字符中 mygo 出现的次数 + ，

再考虑第 个字符加进去后产生的贡献，如果 s[i] == o ,则只要前 个字符产生的字符串的后缀是 'myg',就可以产生贡献。

所以 f[i][1] = f[i-1][0] + f[i-1][1] + 前 i-1 个中选的方案中后缀为 myg 的方案数量 * (s[i] == 0)

现在我们只需要考虑如何处理出 '前 i-1 个中选的方案中后缀为 myg 的方案数量' 即可。

后缀 myg 可由 my 变化过来，my 可由 m 变化过来，m 可由任意后缀变化过来，所以我们一共要维护四种后缀的数量，我们不妨用 3、2、1、0 来代表上面四种后缀（0 代表除了前三种后缀的其他后缀）。

这四个状态的转移关系如下图（有点多，但不难分析）：

我们定义转态 g[i][0/1][0/1/2/3] 为 只考虑前 i 个，第 i 个不选（选），后缀状态为 0/1/2/3 的方案数。

根据上面的图可以很快的得出转移方程。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 100;
const int mod = 1e9 + 7;

int n;
int g[N][2][4],f[N][2];
string s;

signed main()
{
    cin >> s;
    n = s.size();
    s = " " + s;
    if(s[1] == 'm')
    {
        g[1][1][1] = 1;
        g[1][0][0] = 1;
    }
    else 
    {
        g[1][1][0] = 1;
        g[1][0][0] = 1;
    }
    for(int i=2;i<=n;i++)
    {
        g[i][0][0] = g[i-1][1][0] % mod;
        g[i][0][1] = g[i-1][1][1] % mod;
        g[i][0][2] = g[i-1][1][2] % mod;
        g[i][0][3] = g[i-1][1][3] % mod;
        g[i][1][0] = (g[i-1][0][0] * (s[i] != 'm') + g[i-1][0][1] * (s[i] != 'm' && s[i] != 'y') + g[i-1][0][2] * (s[i] != 'm' && s[i] != 'g') + g[i-1][0][3] * (s[i] != 'm') 
                    + g[i-1][1][0] * (s[i] != 'm') + g[i-1][1][1] * (s[i] != 'm' && s[i] != 'y') + g[i-1][1][2] * (s[i] != 'm' && s[i] != 'g') + g[i-1][1][3] * (s[i] != 'm')) % mod;
        g[i][1][1] = (g[i-1][0][0] * (s[i] == 'm') + g[i-1][0][1] * (s[i] == 'm') + g[i-1][0][2] * (s[i] == 'm') + g[i-1][0][3] * (s[i] == 'm') 
                    + g[i-1][1][0] * (s[i] == 'm') + g[i-1][1][1] * (s[i] == 'm') + g[i-1][1][2] * (s[i] == 'm') + g[i-1][1][3] * (s[i] == 'm')) % mod;
        g[i][1][2] = (g[i-1][0][1] * (s[i] == 'y') + g[i-1][1][1] * (s[i] == 'y')) % mod;
        g[i][1][3] = (g[i-1][0][2] * (s[i] == 'g') + g[i-1][1][2] * (s[i] == 'g')) % mod;
    }
    
    for(int i=1;i<=n;i++)
    {
        f[i][0] = f[i-1][1] % mod;
        f[i][1] = (f[i-1][0] + f[i-1][1] + g[i-1][0][3] * (s[i] == 'o') + g[i-1][1][3] * (s[i] == 'o')) % mod;
    }
    int ans = (f[n][0] + f[n][1]) % mod;
    cout << ans << '\n';
}
···