ARC066 简要题解
A
直接模拟即可
B
首先容易得到 (a + b geq a xor b)
设 (f[i][j]) 代表考虑了二进制下 (a, b) 的前 (i) 位, (a + b leq j) 的方案数
那么考虑这样一个事情, 考虑第 (i) 位怎么算, 设前 (i - 1) 位的和为 (j')
一种是 (a, b) 的第 (i) 位均为 (1) , 那么有 (2j' + 2 leq j)
要么只有一个为 (1) , 那么有 (2 j' + 1 leq j)
要么全为 (0) , 那么有 (2j' leq j)
所以有 (f[i][j] = f[i - 1][frac{j}{2}] + f[i - 1][frac{(j - 2)}{2}] + f[i - 1][frac{j - 1}{2}])
除号均为下取整, 这样其实是 (O(log N)) 的
C
加号后的一个括号没用, 减号后的一个括号会把括号中的符号全部变号
然后会发现两个以上的括号嵌套是没用的, 所以括号的嵌套最多只有两个
这样就好算了, 设 (f[i][0 / 1 / 2]) 为前 (i) 个数, 前面还有 (0 / 1 / 2) 个左括号没有匹配, 转移方程比较简单
D
太长了, 懒得更, 洛谷上的题解讲得挺好的