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}\)
分情况讨论:

• 当 \(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

[code]#include #include #include #include #include using namespace std;#define DLN(x) cout