https://www.hackerrank.com/challenges/prime-xor/problem
https://suzyz.github.io/2017/09/16/prime-xor/
https://suzyz.github.io/2017/09/16/prime-xor/
Given an array A with N integers between 3500 and 4500, find the number of unique multisets that can be formed using elements from the array such that the bitwise XOR of all the elements of the multiset is a prime number.
Solution
First, we notice that 3500 ≤ a[i] ≤ 4500. So the bitwise XOR of any multiset is in the range [0,(2^13)-1].
Let count[i] be the number of i in array A.
Let f[i,j] be the number of unique multisets whose elements are within [3500,i], and whose XOR equals to j. So we have
Let f[i,j] be the number of unique multisets whose elements are within [3500,i], and whose XOR equals to j. So we have
f[i,j] = ((f[i-1,j] × (count[i]/2 + 1)) % mo + (f[i-1,j^i] × ((count[i]+1)/2) % mo)) %mo
int n,count[maxd];bool is_prime[max_xor+2];long long f[2][max_xor+2];void init(){for(int i=2;i<=max_xor;i++) is_prime[i]=true;for(int i=2;i<=max_xor;i++)if(is_prime[i]){int j=i<<1;while(j<=max_xor){is_prime[j]=false;j+=i;}}}int main(){init();int T;scanf("%d",&T);while(T){T--;memset(count,0,sizeof(count));memset(f,0,sizeof(f));scanf("%d",&n);int tmp;for(int i=1;i<=n;i++){scanf("%d",&tmp);count[tmp]++;}f[0][0]=1;int flag=1;for(int i=3500;i<=4500;i++){for(int j=0;j<=max_xor;j++)if(count[i]==0)f[flag][j]=f[1-flag][j];elsef[flag][j] = (f[1-flag][j]*(count[i]/2 + 1) % mo + f[1-flag][j^i]*((count[i]+1)/2) % mo) % mo;flag=1-flag;}long long ans=0;for(int j=0;j<=max_xor;j++)if(is_prime[j])ans = (ans + f[1-flag][j])%mo;printf("%lld\n",ans);}
This problem can be solved using dynamic programming and pigeonhole principle. Using sieve of Eratosthenes, mark all the primes lying between to . Create a hashmap which stores the count of occurrences of all the array elements. Note that since the xor-sum of any subset of array elements will not exceed . Using this property, we can write a dynamic programming solution with constant factor such that would store the count of subsets that can be formed with the first elements such that the xor-sum of the elements in the subset is .
int a[5025];
vector<int> v;
bool prime[9025];
long long mem[2][8192];
void sieve( )
{
memset(prime, true, sizeof(prime));
prime[1]=false, prime[0]=false;
for(int i=4;i<=9000;i+=2)
prime[i]=false;
for (int p=3; p*p<=9000;p+=2)
{
if (prime[p] == true)
{
for (int i=p*p; i<=9000; i += 2*p)
prime[i] = false;
}
}
}
int main() {
//freopen("input2.txt","r",stdin);
//freopen("output2.txt","w",stdout);
clock_t begin, end;
begin = clock();
int t;
sieve();
cin >> t;
while(t--) {
int n;
cin >> n;
v.clear();
memset(a,0,sizeof(a));
for(int i=0;i<n;i++) {
int x;
scanf("%d",&x);
a[x]+=1;
}
for(int i=3500;i<4525;i++)
if(a[i]>=1)
v.push_back(i);
memset(mem,0,sizeof(mem));
mem[0][0]=1;
int flag=1;
int k = v.size();
for(int i=1;i<=k;i++) {
for(int j=0;j<8192;j++) {
mem[flag][j] = (mem[flag^1][j]*(1+(a[v[i-1]])/2))%mod + (mem[flag^1][j^v[i-1]]*((a[v[i-1]]+1)/2))%mod;
if(mem[flag][j]>=mod)
mem[flag][j]%=mod;
}
flag = flag^1;
}
long long ans=0;
long long res=0;
for(int i=1;i<8192;i++) {
if(prime[i]){
res+= mem[flag^1][i];
res%=mod;
}
}
cout << res << endl;
}
end = clock();
//cout << ((float) (end) - (float) (begin)) / CLOCKS_PER_SEC << endl;
fclose(stdout);
return 0;Explanation of Flag
This is a standard approach to reduce memory usage when using dynamic programming.
The idea is that often each row of a DP array only depends on the previous row. In this case, instead of storing the whole 2d DP[i][j] array, you can instead just use 2 rows of the array.
In other words, DP[i][j] is stored in mem[0][j] if i is even, and in mem[1][j] if i is odd. The mem array is reused multiple times and after each iteration holds the most recent two rows of the full DP array.
Explanation of recurrence
Suppose we have 5 duplicates of a certain value v. There are 1+5/2 ways of making an xor of 0 (take either 0,2 or 4 copies). There are (1+5)/2 ways of making an xor of v (take either 1,3 or 5 copies).
So to make the new value j, we can either start with j and add 0,2 or 4 copies of v, or start with j^v and add 1,3 or 5 copies
