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\)
总结一下, 就是
\
\
还有最后一个问题, 初始化. 显然当 \(A_1=1, dp_{1, 1} = 1\), 当 \(A_1 = 0, dp_{1,0} = 1\). 换句话说就是 \(dp_{1,A_1}=1\)
CODE
#include #include #include #include #include using namespace std;#define DLN(x) cout
页:
[1]