题解 | #小美的区间异或和#

  个人感觉这题不太像是面试的题目更像是算法竞赛中的题目风格，在面试题目中应该算是比较难的那档
了，感觉很多面试的题单中对于这种位运算思维的计数dp都没怎么练过。
  本人是算法竞赛的选手，首先看到这题的求的计数，存在明显的递推关系，考虑定义状态dp[i]表示以i结
尾的所有连续子数组的贡献。接着我们考虑如何转移这个dp，不难发现，dp[i - 1]的贡献在dp[i]时都
会产生，可以画个图自己思考下，我们令dp[i] = dp[i - 1]，但此时我们还没有考虑我们对新添加的数
字对于答案的贡献，我们不能再合理的时间复杂度内维护每个数字的出现次数，所以考虑按位拆分，统计
二进制中每一位的出现次数，可以发现对于第i个数字令dp[i]比dp[i - 1]而言新增的贡献就是pre(1, 
i - 1) pre(2, i - 1), pre(3, i - 1).... pre(i - 1, i -1)，与这些异或的结果。pre(a, b)表
示区间a到b中所有数字每个位的出现次数（每个位都要维护一个pre），这是可以通过前缀和直接处理出
来的。至此题目完全被解决。
   时间复杂度O(nlgv)

constexpr ll mod = 1e9 + 7;

void solve(){
    int n;
    std::cin >> n;
    std::vector<ll> cur(n + 1, 0);
    for(int i = 1; i <= n; i++)
        std::cin >> cur[i];
    std::vector<std::vector<std::vector<ll>>> pre(n + 1, std::vector<std::vector<ll>>(31, std::vector<ll>(2, 0)));
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= 30; j++){
            for(int k = 0; k <= 1; k++)
                pre[i][j][k] = pre[i - 1][j][k];
            int val = ((cur[i] >> j) & 1);
            pre[i][j][val] += i;
        }
    }

    std::vector<ll> dp(n + 1, 0);
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i - 1];
        for(int j = 0; j <= 30; j++){
            int val = ((cur[i] >> j) & 1);
            dp[i] = (dp[i] + pre[i - 1][j][!val] * (1LL << j) % mod) % mod;
        }
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans = (ans + dp[i]) % mod;
    }
    std::cout << ans << endl;
}