Algorithm

HackerRank/Algorithm/Dynamic Programming/Prime XOR

Problem Summary

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

f[i,j] = ((f[i-1,j] × (count[i]/2 + 1)) % mo + (f[i-1,j^i] × ((count[i]+1)/2) % mo)) %mo

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
const int maxn = 100002;
const int maxd = 4502;
const int mo = 1e9+7;
const int max_xor = (1<<13)-1;
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];
			else
				f[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);
}
    return 0;
}