It seems to me that if there exists a solution, then there exists infinitely many solutions. For, given a solution S, simply add two occurances of any element to S. For instance, S + {3501, 3501} will also be a solution, and by the definition of multisets is a distinct multiset from S.

Finally got AC by DP, some of my thoughts here:

Note the uppper bound of N is 1e5, it tells us to come up with a linear or NlogN solution for each case, but I failed.

So let's look at the range of a[i], it's in [3500, 4500], much smaller than range of N, furthermore, the XOR of any multiset must be in range [0, 8191] (8191==2^13-1). These two observations are the key to my DP solution:

Count the number of each unique integer in input array, then for each unique number, I enumerate every possible integer in [0, 8191] and do some simple calculation to get the number of multiset.

The time complexity of my DP solution is O(M*P), M is the number of unique input integers, P is the range of possible XOR sum, so the upper bound of N*M is 1e7, quite resonable.

I have implemented the same solution in Java and Python 2, and the Python solution times out on some larger cases while the Java solution works. My solution is the same as the editorial. It also seems like no one has submitted a Python solution which gets full score, so it seems like the constraints make it impossible to solve in Python.

Finally AC...this is my attempt written in C++14

#include<bits/stdc++.h>
#define LL long long
#define M 1000000007
using namespace std;

int q, n, f[8200] = {0};
LL dp[1005][8200] = {0}, cnt[1005] = {0};
vector<int> P;

void makePrime(){
    f[0] = f[1] = 1;
    for(int i=2; i*i < 8200; i++){
        if(!f[i]){
            for(int j=i+i; j< 8200; j+=i)
                f[j] = 1;
        }
    }
    for(int i=2; i<8200; i++) if(!f[i]) P.push_back(i);
}

int main() {
    cin >> q;
    makePrime();

    while(q--){
        cin >> n;
        memset(cnt, 0, sizeof(cnt));
        memset(dp,0,sizeof(dp));
        
        for(int i=0,x; i<n; i++) cin >> x, cnt[x-3500]++;
        
        dp[0][3500] = (cnt[0] + 1)/2;
        dp[0][0] = (cnt[0] + 2) / 2;
        for(int i=1; i<1005; i++){
            for(int j=0; j<8200; j++){
                dp[i][j] = (dp[i-1][j]*((cnt[i]+2)/2) + dp[i-1][j^(i+3500)]*((cnt[i]+1)/2) ) % M ;
            }
        }
        LL ans = 0;
        for(int p : P){
            (ans += dp[1004][p]) %= M;
        }
        cout << ans%M << endl;
    }
    return 0;
}

A simple solution in Python is below. It unfortunately times out in larger test cases despite runtime complexity being the same as other solutions.

Note that the solution below uses less space than other solutions that store a full two dimensional array for dynamic programming.

from collections import Counter
import sys

def isPrime(x):
    if x == 1:
        return False
    
    if x == 2:
        return True
    
    for d in range(2, max(2, int(x**0.5)) + 1):
        if x%d == 0:
            return False
    return True


def get_nevens(y):
    return y//2 + 1


def get_nodds(y):
    return y//2 + y%2


def primeXor(a):
    n = len(a)
    c = Counter(a) 
    E = list(c.keys())
    M = 8192

    Sp = [0] * M
    Sn = [0] * M
    e = E[0]

    Sp[e] = get_nodds(c[e])
    Sp[0] = get_nevens(c[e])


    for e in E[1:]:
        for x in range(0, M):
            Sn[x^e] += Sp[x] * get_nodds(c[e])
            Sn[x] += Sp[x] * get_nevens(c[e])

        # next
        Sp = Sn
        Sn = [0] * M

    result = 0 
    for e in range(0, M):
        if isPrime(e):
            result += Sp[e]

    return int(result%(1e9 + 7))

The key to understand the dynamic programming solution is that the solution needs not propagate the "primeness". In other words, dynamic programming in this case is not aware of anything being prime. It merely propagates all possible XOR sums (i.e. 0 to 8192 - 1) and later tallies up which XOR sums are primes. A more technical way of saying is that optimal substructure does not involve primeness but rather simple XOR sums.

What is the role of flag in the editorial?

This times out on the last 4 test cases in Java, but passes when written in c++, is there anything obviously wrong with something I'm doing in Java?

import java.util.*;

public class PrimeXor {
    private static long mod = 1000000007;

    private static List<Integer> getPrimes(int max) {
        List<Integer> prime_list = new ArrayList<>();
        boolean[] primes = new boolean[max];
        Arrays.fill(primes, true);
        primes[0] = false;
        primes[1] = false;

        for (int i = 0; i < primes.length; i++) {
            if (primes[i]) {
                prime_list.add(i);
                for (int inner = i * 2; inner < primes.length; inner += i) {
                    primes[inner] = false;
                }
            }
        }

        return prime_list;
    }

    public static void main(String[] args) {
        List<Integer> primes = getPrimes(8192);
        Scanner scn = new Scanner(System.in);

        int queries = scn.nextInt();
        for (int query = 0; query < queries; query++) {
            int values = scn.nextInt();
            long dp[][] = new long[1000][8192];
            long element_counts[] = new long[3500];

            for (int value = 0; value < values; value++) {
                element_counts[scn.nextInt() - 3500]++;
            }

            dp[0][0] = (element_counts[0] + 2) / 2;
            dp[0][3500] = (element_counts[0] + 1) / 2;

            for (int numbers = 1; numbers < dp.length; numbers++) {
                for (int primes_nums = 0; primes_nums < dp[numbers].length; primes_nums++) {
                    dp[numbers][primes_nums] = (((dp[numbers - 1][primes_nums]) % mod) * (((element_counts[numbers] + 2) / 2) % mod))
                            + ((dp[numbers - 1][(numbers + 3500) ^ primes_nums] % mod) * (((element_counts[numbers] + 1) / 2) % mod));
                }
            }

            long total_sum = 0;
            for (Integer prime : primes) {
                total_sum = ((total_sum % mod) + (dp[dp.length - 1][prime] % mod)) % mod;
            }
            
            System.out.println(total_sum);
        }
    }
}

In mem[flag^1][j^v[i-1]]*odd why j^v[i-1] is used to store value

  what is wrong in my solution ?
          #include<bits/stdc++.h>

using namespace std;

define ll long long int

define testcase while(t--)

define mod 1000000007

int main() { bool table[10000]; memset(table,true,sizeof(table)); for(ll i=2;i*i<=10000;i++) { if(table[i]==true) { for(ll j=i*i;j<=10000;j+=i) table[j]=false; } } ll t; cin>>t; testcase { int n; cin>>n; ll a[n]; mapmap2; ll count=0; map::iterator it; for(ll i=0;i>a[i]; }

ll prev=0;

ll b[n+1]; b[-1]=0; for(ll i=0;i<=n;i++) { b[i]=(a[i]^prev); prev=a[i]; }

 for(ll i=0;i<=n;i++) {
     for(ll j=i;j<=n;j++) {
     if(table[b[j]^b[i-1]])
map2[b[j]^b[i-1]]++;
     }
 }

cout<<(count%mod+map2.size()%mod)%mod<<"\n"; } }

what is wrong inthis code, i think everything is implemented according to the editorial..but still i am getting a wrong ans..plz help.. Thanks..

include

using namespace std;

define ll long long

define mod 1000000007

bool prime[8193]; void sieve() { ll i,j; memset(prime,true,sizeof(prime)); prime[0]=false; prime[1]=false; for(i=2;i*i<=8192;i++) { if(prime[i]) { for(j=2*i;j<=8192;j+=i) prime[j]=false; } } } void solve() { ll n,i,j; cin>>n; vectorv(n); int m[5000]={0}; int dp[2][8192]={0};

for(i=0;i<n;i++)
{
    cin>>v[i];
    m[v[i]]++;

}

dp[0][0]=1;
int flag=1;

for(i=0;i<n;i++)
{
    for(j=0;j<8192;j++)
    {
        //i.e the element occurs even times.., the result will the same as the including just the previous elements.
        ll excluded = (((m[v[i]]/2)+1)*(dp[flag^1][j]))%mod; 

        //i.e the element occurs odd times.., the result will number of ways to find the sum (j^a[i]) with the                  //help of i-1 elements... since a^b=j(wanted)..to find b a^b^a=j^a--> b=j^a            
        ll included = (((m[v[i]]+1)/2)*(dp[flag^1][j^v[i]]))%mod; 

        dp[flag][j]=(included+excluded)%mod;
        //cout<<dp[flag][j]<<" ";
    }
    flag=flag^1;
}
ll ans=0;
for(i=0;i<8192;i++)
{
    //cout<<dp[flag][i]<<" ";
   if(prime[i])
   {
       //cout<<dp[i]<<" ";
        ans=(ans+dp[flag^1][i])%mod;
   }
}
cout<<ans;

} int main() { // your code goes here ll t; cin>>t; sieve(); while(t--) { solve(); } }