题解 CF1408I 【Bitwise Magic】

· · 题解

考虑观察数列 x \oplus (x-1) , (x-1) \oplus (x-2) \cdots (x-k+1) \oplus (x-k) .

可以发现如果对 x 这个数进行了 k' 次减少操作 , 那么就是把整体的异或异或了 x 所对应的数列的长度为 k' 的前缀。

考虑事先异或上所有 a_i 的异或和，那么问题可以转化为 : 对于每个 x , 只能取它对应的数列x \oplus (x-1) , (x-1) \oplus (x-2) \cdots (x-k+1) \oplus (x-k) .的一段前缀，求取出来的部分的异或和为 0 \cdots 2^c 的方案数。

不难发现数列 x \oplus (x-1) , (x-1) \oplus (x-2) \cdots (x-k+1) \oplus (x-k) 中的数都是形如 2^d - 1 的形式，记 Logk = \lceil \log_2{k}\rceil , 这个数列对于任意的 x ，都最多只有一个 2^d-1 中的 d > Logk .

把完全相同的数列合并到一起，不同的数列一共只有 192 种。

对于这 192 种数列进行 DP 预处理，具体是记 f_{0/1,v,i,now} 为当前决策到第 i 位，前 i 位被选中的数有 now 个，当前异或出来的结果低于 2^{Logk} 的位置为 v , 高于 2^{Logk} 的位置是否有值， 0/1,v 可以唯一确定异或出来的数。

然后把所有的 DP 预处理出来的结果 FWT 合并即可。

如果先多项式 \ln 再用加法来实现这个合并的过程，可以达到一个很优秀的复杂度，参见 EI的提交 , 最慢的点只跑了 77ms .

我没有使用多项式 \ln 的代码运行时间 1000+ms .

code 见我的提交1

使用多项式 \ln 之后效率提升至 78ms .

code 见我的提交2