题意很明白，不复述了吧 qwq
solution
一个数 \(a_i\) 减去 \(\Delta\) 之后对整个数组的异或和会造成 \(a_i~\text{xor}~(a_i-\Delta)\) 的影响。所有数的影响 \(\text{xor}\) 起来就是对整个数组的影响总和。
值域不大可以塞到 dp 状态里，已经减去的总和也可以塞进去。就设计出状态 \(dp_{i,j,msk}\) 表示考虑前 \(i\) 个数，总共减去了 \(j\)，总影响是 \(msk\) 的方案数。
直接背包做，第一维可以滚掉，复杂度 \(O(2^cnk^2)\)，是不能够的。
由于输入的数组是无序的，所以可以想办法按一种顺序排，优化 dp。
第一维肯定没啥可优化的。比较大的就剩 \(msk\) 了。
注意一下数据的其他性质：
-
输入的数组中所有数均不相同。
-
\(k\) 很小。
观察到一个数 \(x\) 减去 1 造成的影响 \(x~\text{xor}~(x-\Delta)\) 的位数几乎不超过 \(x\) 的 \(\text{lowbit}\) 的位数，除非 \(x\) 的 \(\text{lowbit}\) 在最低几位。
而满足减去 \([1,k]\) 中一个数后 \(\text{lowbit}=2^p\) 的数只有 \(O(\dfrac{2^c}{2^p}k)\) 个。如果状态第三维的总和是 \(\sum 2^p O(\dfrac{2^c}{2^p}k)=O(2^cck)\) 就可以接受了！
为了保证 dp 可以正常转移，我们把所有 \(a_i\) 按照其减去 \([1,k]\) 内能产生的影响的最大值从小到大排序，这样就可以正确转移了。
复杂度是 \(O(2^cck^3)\)，可以通过。
code
Submission #238945073 - Codeforces
标签：xor,text,减去,CF1408I,Delta,msk,dp From： https://www.cnblogs.com/FreshOrange/p/17931464.html