Divan and bitwise operations

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

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

题解：

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

考虑二进制第 $i$ 位对"数组所有子序列异或值的和"的贡献。设 $a_1,a_2\cdots a_n$ 中第 $i$ 位等于1的个数为 $a$ ，从中取奇数个异或后第 $i$ 位仍为1，对答案有贡献。所以总贡献为 $2^{a-1}*2^{n-a}*2^{i}$ 。其中 $2^{a-1}$ 表示从 $a$ 个数字中取奇数个数字的方案数， $2^{n-a}$ 表示取第 $i$ 位等于0的方案数， $2^{i}$ 表示每个方案对答案的贡献。所以总贡献为 $2^{n-1+i}$ 。但是上述前提是 $a>0$ 。当 $a==0$ 即所有数字第 $i$ 位都是0时，对答案的贡献是0。如何判断 $a_1,a_2\cdots a_n$ 中第 $i$ 位是否有1？由于每个 $a_i$ 至少出现在一个连续段中，将所有段 $x$ 的或等于 $a_1,a_2\cdots a_n$ 的或。判断或中是否有1即可。