Panda and XOR

QUESTION

Little Black Panda is mad about XOR operation. Presently he has gone mad and he won’t stop performing XOR operation on various numbers.\nGiven an array of N numbers, for each subset of the array Little Panda performs MAXOR operation for the subset. MAXOR operation means that he finds XOR of all elements in that subset (if the subset is [1,2,3] then MAXOR is 1^2^3=0) . \n\nLittle Panda is now exhausted and wants to do something else. Little Panda wants to pick any two subsets the MAXOR of whose are same. \nLittle Panda needs to find the number of selections that he can make. He is very very weak in programming so he wants the answer from you. \n\nPlease help little panda in finding out his query.\nSince the output can be very large output it modulo 1000000007.\n\nInput Format\n\nThe first line contains N i.e. the length of the array.\nN lines follow, each containing a non-negative integer.\n\nOutput Format\n\nOutput Little Panda’s Query in a single line.\n\nConstraints\n1 <= N <= 100000\n0 <= A[i] <= 100\n(where A[i] denotes the value of array element).

ANSWER

#include<stdio.h>
#define FOR(i,a,b) for(i= a ; i < b ; ++i)
#define rep(i,n) FOR(i,0,n)
#define INF INT_MAX
#define ALL(x) x.begin(),x.end()
#define LET(x,a) __typeof(a) x(a)
#define IFOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define EACH(it,v) IFOR(it,v.begin(),v.end())
#define pb push_back
#define sz(x) int(x.size())
#define mp make_pair
#define fill(x,v) memset(x,v,sizeof(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define si(n) scanf("%d",&n)
#define pi(n) printf("%d ",n)
#define pd(n) printf("%lf ",n);
#define pdl(n) printf("%lf\n",n);
#define pin(n) printf("%d\n",n)
#define pln(n) printf("%lld\n",n)
#define pl(n) printf("%lld ",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define scan(v,n) vector<int> v;rep(i,n){ int j;si(j);v.pb(j);}
#define mod (int)(1e9 + 7)
#define ll long long int
#define F first
#define S second
ll modpow(ll a,ll n,ll temp){ll res=1,y=a;while(n>0){if(n&1)res=(res*y)%temp;y=(y*y)%temp;n/=2;}return res%temp;} 
ll arr[100006],flagit[134],flg[134];
inline ll checkit(ll calc)
{
 if(calc>=mod)
  calc%=mod;
 return calc;
}
inline ll chck(ll calc)
{
 while(calc<0)
  calc+=mod;
 calc%=mod;
 return calc;
}
int main()
{
 ll n,calc,calc1,i,j,sz,c1,c2,ans=0;
 sl(n);
 rep(i,n)
 {
  sl(arr[i]);
 }
 rep(i,135)
  flagit[i]=0;
 rep(i,n)
 {
  rep(j,135)
   flg[j]=0;
  rep(j,129)
  {
   if(flagit[j]!=0)
   {
    calc=j^arr[i];
    //printf("i=%d j=%d calc=%d\n",i,j,calc);
    flg[calc]+=flagit[j];
    flg[calc]=checkit(flg[calc]);
   }
  }
  rep(j,129)
  {
   //printf("i=%d calc=%d calc1=%d\n",i,calc,calc1);
   flagit[j]+=flg[j];
   flagit[j]=checkit(flagit[j]);
  }
  flagit[arr[i]]++;
  flagit[arr[i]]=checkit(flagit[arr[i]]);
 }
 c2=modpow(2,mod-2,mod);
 //pln(c2);
 rep(i,129)
 {
  //printf("i=%d flagit=%d\n",i,flagit[i]);
  calc=flagit[i];
  c1=calc*(calc-1);
  c1=chck(c1);
  c1=c1*c2;
  c1=checkit(c1);
  ans+=c1;
  ans=checkit(ans);
 }
 pln(ans);
 return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.