In this HackerEarth Zero Xor problem solution, A Zero Xor Subset is a non-empty subset having Xor of all the elements in it equal to 0.
Now you are given an array of N numbers.
You have to count the number of different Zero Xor Subsets of this array.


HackerEarth Zero Xor problem solution


HackerEarth Zero Xor problem solution.

#include<bits/stdc++.h>
using namespace std;
#define test() int t;scanf("%d",&t);for(int tno=1;tno<=t;tno++)
#define mp make_pair
#define pb push_back
#define wl(n) while(n--)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long ll;
typedef unsigned long long llu;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > piii ;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
#define sz(a) int((a).size())
#define ini(a,v) memset(a,v,sizeof(a))
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scl(x) scanf("%lld",&x)
#define scl2(x,y) scanf("%lld%lld",&x,&y)
#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define scs(s) scanf("%s",s);
#define gcd __gcd
#define debug() printf("here\n")
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define MOD 1000000007
#define inf ((1<<29)-1)
#define linf ((1LL<<60)-1)
const double eps = 1e-9;

const int MAX = 45;

ll a[MAX]={0};

int main()
{
int i,j,k;
ll n;
scl(n);
chk(n);
for(i=0;i<n;i++){
scl(a[i]);
chk2(i,a[i]);
}
for(i=0;i<n;i++){
chk2(i,a[i]);
}
int x = (n+1)/2;
int y = n - x;
vector<ll>v1,v2;
for(i=0;i<x;i++){
v1.pb(a[i]);
}
for(;i<n;i++){
v2.pb(a[i]);
}
int s1 = (1<<x);
map<ll,ll>mapp1,mapp2;
for(i=1;i<s1;i++){
int l = i;
int ind = v1.size() - 1;
int xx = 0;
while(l){
if(l&1){
xx ^= v1[ind];
}
ind--;
l/=2;
}
mapp1[xx]++;
}
int s2 = (1<<y);
chk2(s1,s2);
for(i=1;i<s2;i++){
int l = i;
int ind = v2.size() - 1;
int xx = 0;
while(l){
if(l&1){
xx ^= v2[ind];
}
ind--;
l/=2;
}
mapp2[xx]++;
}
ll ans = mapp1[0] + mapp2[0];
map<ll,ll>::iterator it = mapp1.begin();
while(it!=mapp1.end()){
ll c1 = it->se;
ll x = it->fi;
ll c2 = mapp2[x];
ans = ans + c1*c2;
it++;
}
assert(ans>=0&&ans<=INT_MAX);
printf("%lld\n",ans);
return 0;
}