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 感谢分享，下载保存了，貌似很强大 感谢分享 懂技术并乐意极积无私分享的人越来越少。珍惜 收藏一下 不知道什么时候能用到 感谢发布原创作品，程序园因你更精彩 感谢分享，学习下。 这个好，看起来很实用 收藏一下 不知道什么时候能用到 分享、互助 让互联网精神温暖你我 谢谢楼主提供！ 很好很强大我过来先占个楼 待编辑 用心讨论，共获提升！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 谢谢分享，辛苦了 很好很强大我过来先占个楼 待编辑 yyds。多谢分享 热心回复！ 过来提前占个楼 前排留名，哈哈哈
页:
[1]
2