美团笔试0909 异或和题思路分享

比较幸运今早思路很清晰，很顺地a出了最后这道题。
我的思路是用一个二维数组cnt[32][2]保存在当前位置之前，每个二进制位置上0和1的贡献，用一个数组dp[i]保存数组arr[0]到arr[i]中所有子数组的异或和。val[i]保存的是2的i次方。
每次遍历到一个数arr[i]，根据之前各个位置上0和1的贡献，计算出dp[i]。dp[i]的计算主要分两部分，一部分是包括当前数字arr[i]的所有计算，公式为dp[i] += val[k] * cnt[k][!cur]，k是当前数字二进制表示的第k位，cur是这个位置上的数（0或1），这个过程需要遍历数字arr[i]的每一个二进制位；另一部分是不包括当前数字arr[i]的计算，这部分直接dp[i] += dp[i-1]。计算完dp[i]后，需要更新一下cnt数组，当前数字二进制第k位上是0，那么cnt[k][0] += i + 1，如果是1同理，这个过程就是计算当前数字对后面计算的一个贡献。最后的结果就是求dp数组的和。我在整个过程中为了避免溢出使用的都是long long，还有注意求余。
手机码字，如有错误，欢迎提出