Divan and bitwise operations


这是一道比较综合的数学题目,光是吧题目看懂就花了我好一会儿时间,先看看题目吧:

 

题目分析:对于m段给定连续段的或值,要求出n个数的序列子序列的异或值之和;

题解:

这道题,我们先不要把它当作一个数一个数来做,而是要考虑每一位的贡献值;

考虑二进制第 [公式] 位对"数组所有子序列异或值的和"的贡献。设 [公式] 中第 [公式] 位等于1的个数为 [公式] ,从中取奇数个异或后第 [公式] 位仍为1,对答案有贡献。所以总贡献为 [公式] 。其中 [公式] 表示从 [公式] 个数字中取奇数个数字的方案数, [公式] 表示取第 [公式] 位等于0的方案数, [公式] 表示每个方案对答案的贡献。所以总贡献为 [公式] 。但是上述前提是 [公式] 。当 [公式] 即所有数字第 [公式] 位都是0时,对答案的贡献是0。如何判断 [公式] 中第 [公式] 位是否有1?由于每个 [公式] 至少出现在一个连续段中,将所有段 [公式] 的或等于 [公式] 的或。判断或中是否有1即可。

代码:Submission #153711607 - Codeforces