ABC310E NAND repeatedly 题解

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}\)

分情况讨论:

1. 当 \(A_i=0\) 时, 考虑 \(dp_{i, 0}\):
   1. 对于任何 \(x \in \{0, 1\}, x \barwedge 0 \neq 0\), 所以加上 \(0\)
   2. 对于新增的 \(f(i, i)\), \(f(i,i) = A_i = 0\), 所以加上 \(1\)
      所以此时 \(dp_{i, 0} = 0 + 1 = 1\)
2. 当 \(A_i = 1\) 时, 考虑 \(dp_{i,0}\):
   1. 对于 \(x = 1\), \(x \barwedge 0 = 0\), 所以加上 \(dp_{i-1,1}\)
   2. 对于新增的 \(f(i, i)\), \(f(i,i) = A_i = 1\), 所以加上 \(0\)
      所以此时 \(dp_{i, 0} = dp_{i - 1, 1} + 0 = dp_{i - 1, 1}\)
3. 当 \(A_i=0\) 时, 考虑 \(dp_{i, 1}\):
   1. 对于任何 \(x \in \{0, 1\}, x \barwedge 0 = 1\), 所以加上 \(dp_{i - 1, 1} + dp_{i - 1, 0}\)
   2. 对于新增的 \(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}\)
4. 当 \(A_i = 1\) 时, 考虑 \(dp_{i,1}\)
   1. 对于 \(x = 0, x \barwedge 1 = 1\), 所以加上 \(dp_{i-1, 0}\)
   2. 对于新增的 \(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\)

#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 long

signed 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;
}