题解：CF2252E Generational Triplets

· · 题解

CF 官解神秘地倒腾了几下式子就出来了，现在题解区又是利用超强注意力注意到打表出的规律，这里给点人能写出来的东西吧。

首先这种数位 dp 相关的题，从最高位看总是合适的。考虑 b 的最高位一定与 c 相同，如果不相同那异或出来就是 1 了，由此 a 最高位又不能与 b 和 c 相同，不然异或出来也是 1。于是最高位那里一定 c,b,a 一定分别是 1,1,0。

然后往下一位，尝试利用等差的性质舍掉一些情况。0,1,1 大小关系不满足肯定不行。设最高位对应 2^p，1,1,0 的话 c-b \lt 2^{p-1},b-a \gt 2^{p}，就不可能等差了。0,0,0 时 b-a \gt 2^{p-1}，同样也不行。于是固定填 1,0,1 了。这样前两位就分别是 11,10,01。

然后你发现最高两位正好是等差的，也就是说我们只需要后面等差且异或和为 0 就好了！因为前两位已经把大小固定了，后面没有大小的限制，等价于把原本的 a,b,c 的填法倒过来也可以。基于此，有显然的 a,b,c 构造方式，即先填个 11,10,01，然后若干 0,0,0，然后 11,10,01 或者 01,10,11，然后若干 0,0,0，然后 11,10,01 或者 01,10,11……循环下去。于是自然发现一个 c 至多对应一个 a,b，且 c 必须要由 01,11,0 拼成，且最高两位是 11。数位 dp 即可，状态设为有没有填最高位。

晚上困，实现的很丑