https://atcoder.jp/contests/abc310/tasks/abc310_e
一个奇怪的递归式 + \(N \le 10^6\), 试试动态规划
设 \(dp_{i,j}\) 为对于所有 \(1 \le l \le i\) 满足 \(f(l, i)=j\) 的数量, 其中 \(j \in \{0,1\}\).
最后答案就是 \(\sum\limits_{i=1}^{n}dp_{i,1}\)
分情况讨论:
- 当 \(A_i=0\) 时, 考虑 \(dp_{i, 0}\):
- 对于任何 \(x \in \{0, 1\}, x \barwedge 0 \neq 0\), 所以加上 \(0\)
- 对于新增的 \(f(i, i)\), \(f(i,i) = A_i = 0\), 所以加上 \(1\)
所以此时 \(dp_{i, 0} = 0 + 1 = 1\)
- 当 \(A_i = 1\) 时, 考虑 \(dp_{i,0}\):
- 对于 \(x = 1\), \(x \barwedge 0 = 0\), 所以加上 \(dp_{i-1,1}\)
- 对于新增的 \(f(i, i)\), \(f(i,i) = A_i = 1\), 所以加上 \(0\)
所以此时 \(dp_{i, 0} = dp_{i - 1, 1} + 0 = dp_{i - 1, 1}\)
- 当 \(A_i=0\) 时, 考虑 \(dp_{i, 1}\):
- 对于任何 \(x \in \{0, 1\}, x \barwedge 0 = 1\), 所以加上 \(dp_{i - 1, 1} + dp_{i - 1, 0}\)
- 对于新增的 \(f(i, i)\), \(f(i,i) = A_i = 0\), 所以加上 \(0\)
所以此时 \(dp_{i, 1} = dp_{i - 1, 1} + dp_{i - 1, 0} + 0 = dp_{i - 1, 1} + dp_{i - 1, 0}\)
- 当 \(A_i = 1\) 时, 考虑 \(dp_{i,1}\)
- 对于 \(x = 0, x \barwedge 1 = 1\), 所以加上 \(dp_{i-1, 0}\)
- 对于新增的 \(f(i, i)\), \(f(i,i) = A_i = 1\), 所以加上 \(1\)
所以此时 \(dp_{i, 1} = dp_{i-1, 0} + 1\)
总结一下, 就是
\[dp_{i,0} =
\begin{cases}
1 &(A_i=0) \\
dp_{i-1, 1} &(A_i=1)
\end{cases}
\]
\[dp_{i,1} =
\begin{cases}
dp_{i-1,1} + dp_{i-1,0} &(A_i = 0) \\
dp_{i-1, 0} + 1 &(A_i=1)
\end{cases}
\]
还有最后一个问题, 初始化. 显然当 \(A_1=1, dp_{1, 1} = 1\), 当 \(A_1 = 0, dp_{1,0} = 1\). 换句话说就是 \(dp_{1,A_1}=1\)
CODE
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <array>
using namespace std;
#define DLN(x) cout << #x << "\t = " << x << '\n';
#define CDLN(x, l, r) cout << #x << "\t = [ "; for (int i = l; i <= (int)r; i ++) cout << x[i] << ' '; cout << "]\n";
#define CCDLN(x, l, r, what) cout << #x << "\t = [ "; for (int i = l; i <= (int)r; i ++) cout << (what) << ' '; cout << "]\n";
template <typename T>
using vec = vector<T>;#define int long longsigned main() {int n;string s;cin >> n >> s;vec<array<int, 2>> dp(n + 1);vec<int> arr(n + 1);for (int i = 0; i < s.size(); i ++) arr[i + 1] = s[i] - '0';dp[1][arr[1]] = 1;for (int i = 2; i <= n; i ++) {if (arr[i] == 0) {dp[i][1] = dp[i - 1][1] + dp[i - 1][0];dp[i][0] = 1;}else {dp[i][1] = dp[i - 1][0] + 1;dp[i][0] = dp[i - 1][1];}}int ans = 0;for (int i = 1; i <= n; i ++) ans += dp[i][1];cout << ans << '\n';return 0;
}