【异或和之和 / H】

题目

思路

• 异或前缀和优化到 
  • 计算本身是，这很好
  • 单用前缀和的缺点是我们按照枚举  对计算贡献，分的种类也就是计算的次数达到了 
  • 优化方式是，我们按照枚举各个数位  来计算贡献，这样时间就会达到 
• 拆位法+贡献法
  • 有贡献的是  异或
  • 第  位（从0开始）上的  有序对数目乘以权重  就是对答案的贡献

代码 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5+10;
int s[N];
ll ans;
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> s[i], s[i] = s[i] ^ s[i-1];
    
    for(int i = 0; i < 21; i++)
    {
        ll now = 0;
        int c0 = 0, c1 = 0;
        for(int j = 0; j <= n; j++)
        {
            if((s[j] >> i) & 1) now += c0, c1++;
            else now += c1, c0++;
        }
        
        ans += now * (1 << i);
    }
    
    cout << ans;
}

原文地址：https://blog.csdn.net/m0_73669127/article/details/142730181

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！