Help in Problem E : XOR Sigma

Правка en1, от HuTao_Oya_OyaOya, 2024-08-03 22:04:27

Problem Link

Problem in short : Find sum of XOR of all subarrays of size>1 in the given array of size n in linear time.

My idea is to get the prefix sum array of XORs and now the problem is reduced to finding XOR between all possible pairs in prefix XOR array.

I tried for hours to debug the code but couldn't figure out what did I do wrong. Any help would be greatly appreciated.

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    vector<int>pref(n); pref[0]=v[0];
    for(int i=1;i<n;i++) pref[i]=pref[i-1]^v[i];
    for(int i=0;i<n;i++) v[i]=pref[i];
    ll res = 0;
    vector<vector<int>>set(n,vector<int>(30));
    vector<vector<int>>unset(n,vector<int>(30));
    for(int i=0;i<30;i++) {
        if((v[0]&(1<<i))!=0) set[0][i]=1;
        else unset[0][i]=1;
    }
    for(int i=1;i<n;i++) {
        for(int j=0;j<30;j++) {
            set[i][j] = set[i-1][j]; unset[i][j] = unset[i-1][j];
            if((v[i]&(1<<j))!=0) set[i][j]++;
            else unset[i][j]++;
        }
    }
    for(int i=1;i<n;i++){
        for(int j=0;j<30;j++){
            if((v[i]&(1<<j))!=0) res+=unset[i-1][j]*(1<<j);
            else res+=set[i-1][j]*(1<<j);
        }
    }
    cout<<res;
}

Теги thanks, for, the, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский HuTao_Oya_OyaOya 2024-08-04 02:07:23 103
en2 Английский HuTao_Oya_OyaOya 2024-08-04 02:05:35 783
en1 Английский HuTao_Oya_OyaOya 2024-08-03 22:04:27 1492 Initial revision (published)