题目链接：https://ac.nowcoder.com/acm/contest/58604/G
来源：牛客网
设 \(f[i]\) 表示以 \(s[i]\) 为结尾的合法序列个数
- 如果 \(s[i]\ne 1\) ，那么我们可以在从 \(f[i-1]\) 到 \(f[1]\) 所包含的序列后面添加 \(s[i]\) 构成答案，也可以单独以 \(s[i]\) 为新的合法序列（也就是后面公式中的+1）。即 \(f[i]=(\sum\limits_{j=1}^{i-1} f[j])+1\) 。
- 如果 \(s[i]=1\) ，那么我们可以在从 \(f[i-1]\) 到 \(f[1]\) 中所有不以 \(6\) 为结尾的序列后面添加 \(s[i]\) 构成答案，也可以单独以 \(s[i]\) 为新的合法序列（也就是后面公式中的+1）。即 \(f[i]=(\sum\limits_{j=1}^{i-1} f[j]\ \mathrm{if}\ s[j]\ne 6)+1\) 。
最终答案为 \(\sum_{i=1}^{n}f[i]\) 。
此时复杂度为 \(O(n^2)\) 的。
我们可以维护两个前缀和保存答案
\(pr[i]=pr[i-1]+f[i]\)
\(pr6[i]=pr6[i-1]+ \begin{cases} 0,s[i]=6\\ f[i],s[i]\ne 6 \end{cases}\)
那么 \(f[i]=\begin{cases} pr[i-1]+1,s[i]\ne 1\\ pr6[i-1]+1,s[i]=1 \end{cases}\)
这样的复杂度为 \(O(n)\) 的。
最终答案为 \(\sum_{i=1}^{n}f[i]\) ，也就是 \(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;
}