#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
#include <string>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <functional>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <stack>
#include <utility>
using namespace std;
#define s(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define p(n) printf("%d ",n)
#define pl(n) printf("%lld",n)
#define sf(n) scanf("%f",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define pf(n) printf("%f ",n)
#define pd(n) printf("%lf ",n)
#define ps(n) printf("%s ",n)
#define nl putchar('\n')
#define e1 first
#define e2 second
#define INF (int)1e9
#define MOD 1000000007
#define LINF (ll)1e18
#define EPS 1e-11
const double PI = acos(-1.0)
#define pow2(n) (1<<(n))
#define pow2l(n) ((ll)1<<(n))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(n) ((a)<0?-(a):(a))
#define MAXE(...) max_element(__VA_ARGS__)
#define MINE(...) min_element(__VA_ARGS__)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define RNG(i,n) FOR(i,0,n)
#define REV(i,a,b) for(int i=a;i>=b;--i)
#define FORECH(v,c) for(typeof((c).begin()) v=(c).begin(); v!=(c).end(); ++v)
#define ALL(a) (a).begin(),(a).end()
#define LEN(a) ((int)(a.size()))
#define PB(x) push_back(x)
#define TIMES(x) while((x)--)
#define UPB upper_bound
#define LWB lower_bound
#define MP make_pair
#ifndef ONLINE_JUDGE
#define DEBUG__
#endif
#ifdef DEBUG__
#define derr(x) cerr<<"<"<<#x<<": "<<x<<">"<<endl
#define _DEBUG(...) __VA_ARGS__
;template<typename T> void debug(T a, T b){ for(;a!=b;++a) cerr<<*a<<" "; cerr<<endl; }
#else
#define derr(...)
#define _DEBUG(...)
;template<typename T> void debug(T a, T b){}
#endif
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef list<int> li;
typedef map<int,int> mii;
template<typename T> T modPow(T b, T e, T m=(ll)MOD){T res=1;while(e){if(!(e&0x1))res=(res*b)%m;e>>=1;b=(b*b)%m;}return res; }
template<typename T> T gcd (T u, T v){ return (u==0||v==0||u==v)?(u|v):((~u&1)?((v&1)?gcd(u>>1,v):gcd(u>>1,v>>1)<<1):((~v&1)?gcd(u,v>>1):((u>v)?gcd((u-v)>>1,v):gcd((v-u)>>1,u)))); }
template<typename T> T lcm (T a, T b){ return a*b/gcd(a,b); }
//#undef DEBUG__
/////////////////////////////// FAST IO ///////////////////////////////////////
#define gc getchar_unlocked
void si(int &n){
register int ch=gc();
int neg = 0;
n=0;
while((ch<48||ch>57) && ch!='-')ch=gc();
if(ch=='-'){ neg=1; ch=gc(); }
for(;ch>47 && ch<58; ch=gc()) n = (n<<1)+(n<<3)+ch-48;
if(neg)n=-n;
}
int main() {
// your code goes here
long long int m,n, temp, sum;
int t; cin >> t;
while(t--){
sum = 0;
cin >> n >> m;
long long int mark_b[1024], xor_set[1024], input[1024], xx[1024];
memset(mark_b, 0, sizeof(mark_b));
memset(xor_set, 0, sizeof(xor_set));
memset(xx, 0, sizeof(xx));
for(int i = 0; i < n; i++ ) cin >> input[i];
for(int i = 0; i < m; i++){
cin >> temp; mark_b[temp] = 1;
}
xor_set[0] = 1;
for(int i = 0; i < n; i++){
for(int j = 0 ; j < 1024; j++){
if(xor_set[j]) xx[j ^ input[i]] += xor_set[j] % MOD;
}
for(int k = 0; k < 1024; k++) {
xor_set[k] += xx[k] % MOD; xx[k] = 0;
xor_set[k] %= MOD;
}
if(!xor_set[0]) xor_set[input[i]]++;
}
for(int i= 0; i < 1024; i++){
if(!mark_b[i] && xor_set[i]) sum+= xor_set[i] % MOD;
sum %= MOD;
}
cout << sum % MOD << endl;
}
return 0;
}
I am getting WA for case:
1
100 10
26 134 116 45 6 18 3 1 184 119 129 177 29 32 149 200 123 40 85 196 128 192 188 4 85 191 195 73 98 131 135 108 180 35 164 160 100 89 61 171 124 179 163 2 110 79 46 156 187 194 147 98 44 25 148 29 141 181 82 64 171 145 71 43 0 164 156 5 113 167 159 175 127 66 32 195 62 0 74 45 166 17 24 49 10 152 100 29 78 60 11 193 130 134 158 99 146 38 108 148
55 48 12 16 18 17 18 4 5 9
The answer is 20500166
While I am getting: 797514481
Please help me.
P.S. I will correct my solution's output format. Just tell me if my algorithm is correct or not.
Thanks.