Codeforces Round #473 (Div. 2), problem: (F) Mahmoud and Ehab and yet another xor task Solution In C/C++

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+5;
const int mod =1e9+7;
typedef pair<int,int>pii;
int a[maxn];
int b[25];
int ans[maxn];
int p[maxn];
vector<pii>q[maxn];
int main()
{
int n,m;
cin>>n>>m;
memset(b,-1,sizeof(b));
p[0]=1;
for(int i=1;i<=n;i++)scanf(“%d”,&a[i]),p[i]=p[i-1]*2%mod;
for(int i=1;i<=m;i++)
{
int l,x;
scanf(“%d%d”,&l,&x);
q[l].push_back(make_pair(x,i));
}
for(int i=1;i<=n;i++)
{
int x=a[i];
for(int j=20;j>=0;j–)
{
if(!(x>>j))continue;
if(b[j]==-1)
{
b[j]=x;
break;
}
x^=b[j];
}
int cnt=i;
for(int j=20;j>=0;j–)if(b[j]!=-1)cnt–;
for(int k=0;k<q[i].size();k++)
{
pii t =q[i][k];
int x = t.first;
for(int j=20;j>=0;j–)
{
if(!(x>>j))continue;
if(b[j]==-1)break;
x^=b[j];
}
if(x==0)ans[t.second]=p[cnt];
}
}
for(int i=1;i<=m;i++)printf(“%d\n”,ans[i]);
return 0;
}

(Visited 24 times, 1 visits today)

About the Author:

Leave A Comment