牛客2023年儿童节比赛 G 小红过61

设 $f[i]f[i]$ 表示以 $s[i]s[i]$ 为结尾的合法序列个数

1. 如果 $s[i]\mathrm{\ne }1s[i]\backslash ne\; 1$ ，那么我们可以在从 $f[i-1]f[i-1]$ 到 $f[1]f[1]$ 所包含的序列后面添加 $s[i]s[i]$ 构成答案，也可以单独以 $s[i]s[i]$ 为新的合法序列（也就是后面公式中的+1）。即 $f[i]=({\sum }_{j=1}^{i-1}f[j])+1f[i]=(\backslash sum\backslash limits\_\{j=1\}^\{i-1\}\; f[j])+1$ 。
2. 如果 $s[i]=1s[i]=1$ ，那么我们可以在从 $f[i-1]f[i-1]$ 到 $f[1]f[1]$ 中所有不以 $66$ 为结尾的序列后面添加 $s[i]s[i]$ 构成答案，也可以单独以 $s[i]s[i]$ 为新的合法序列（也就是后面公式中的+1）。即 $f[i]=({\sum }_{j=1}^{i-1}f[j]\mathrm{i}\mathrm{f}s[j]\mathrm{\ne }6)+1f[i]=(\backslash sum\backslash limits\_\{j=1\}^\{i-1\}\; f[j]\backslash \; \backslash mathrm\{if\}\backslash \; s[j]\backslash ne\; 6)+1$ 。

最终答案为 ${\sum }_{i=1}^{n}f[i]\backslash sum\_\{i=1\}^\{n\}f[i]$ 。

此时复杂度为 $O(n^2)O(n^2)$ 的。

我们可以维护两个前缀和保存答案

$pr[i]=pr[i-1]+f[i]pr[i]=pr[i-1]+f[i]$

$pr6[i]=pr6[i-1]+\{\begin{array}{c}0,s[i]=6\\ f[i],s[i]\mathrm{\ne }6\end{array}pr6[i]=pr6[i-1]+\; \backslash begin\{cases\}\; 0,s[i]=6\backslash \backslash \; f[i],s[i]\backslash ne\; 6\; \backslash end\{cases\}$

那么 $f[i]=\{\begin{array}{c}pr[i-1]+1,s[i]\mathrm{\ne }1\\ pr6[i-1]+1,s[i]=1\end{array}f[i]=\backslash begin\{cases\}\; pr[i-1]+1,s[i]\backslash ne\; 1\backslash \backslash \; pr6[i-1]+1,s[i]=1\; \backslash end\{cases\}$

这样的复杂度为 $O(n)O(n)$ 的。

最终答案为 ${\sum }_{i=1}^{n}f[i]\backslash sum\_\{i=1\}^\{n\}f[i]$ ，也就是 $pr[n]pr[n]$ 。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5, mod = 1e9 + 7;

ll f[N], pr6[N], pr[N];
int main() {
    string s;
    s = "2621";
    cin >> s;
    int n = s.size();
    s = " " + s;
    for (int i = 1; i <= n; i++) {
        // s[i]：以第i个字符为结尾的合法子序列个数
        if (s[i] == '1') {
            f[i] = pr6[i - 1] + 1;
        } else {
            f[i] = pr[i - 1] + 1;
        }
        pr[i] = pr[i - 1] + f[i];
        if (s[i] != '6')
            pr6[i] = pr6[i - 1] + f[i];
        else
            pr6[i] = pr6[i - 1];
        pr[i] %= mod;
        pr6[i] %= mod;
        f[i] %= mod;
    }
    cout << pr[n] << endl;
    return 0;
}