G 小红过61

想到dp，先不考虑题目所给条件，遍历输入的字符串s，i表示遍历到的位置，dp[i]表示遍历到当前位置时合法子串的数目，发现遍历到s[i]时，新的子串有两种选择，1、直接在dp[i - 1]表示的每一个子串后面加上s[i]，2、s[i]成为一个独立的子串，即dp[i] = dp[i - 1] * 2 + 1。

显然，遍历到s[i] = '6'时，s[i]不可能出现在任何一个连续的"61"中，所以考虑遍历到s[i] = 1的情况。

当s[i] = '1'时，符合题意的子串数目应该等于当s[i] != '1'时合法子串的数目再减去遍历到s[i]时所有以6结尾的子串数目，用dp6[i - 1]表示遍历到s[i - 1]时所有以6结尾的子串数目，可以得到dp[i] = dp[i - 1] * 2 + 1 - dp6[i - 1]。

显然，dp[0] = 0, dp6[0] = 0, 当且仅当s[i] = '6'时，更新dp6，dp6[i] = dp6[i - 1] + dp[i - 1] + 1，且答案为dp[s.size() - 1]。

同时，注意到更新dp[i]时只会用到dp[i - 1]，dp6同理，所以可以将dp与dp6简化为两个变量，主要代码如下

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    ll ans = 0, s6 = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '1')
            ans = (ans * 2 + 1 - s6 + mod) % mod;
        else
        {
            if (s[i] == '6')
                s6 = (s6 + ans + 1) % mod;
            ans = (ans * 2 + 1) % mod;
        }
    }
    cout << ans << endl;
    return 0;
}