Cerinta completa

Penny has an array of integers, . She wants to find the number of unique multisets she can form using elements from the array such that the bitwise XOR of all the elements of the multiset is a prime number. Recall that a multiset is a set which can contain duplicate elements.

Given queries where each query consists of an array of integers, can you help Penny find and print the number of valid multisets for each array? As these values can be quite large, modulo each answer by before printing it on a new line.

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query in the following format:

  1. The first line contains a single integer, , denoting the number of integers in the array.
  2. The second line contains space-separated integers describing the respective values of .

Constraints

Output Format

On a new line for each query, print a single integer denoting the number of unique multisets Penny can construct using numbers from the array such that the bitwise XOR of all the multiset’s elements is prime. As this value is quite large, your answer must be modulo .

Sample Input

1   
3   
3511 3671 4153

Sample Output

4

Explanation

The valid multisets are:

  • is prime.
  • is prime.
  • is prime.
  • , which is prime.

Because there are four valid multisets, we print the value of on a new line.

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    static final long MOD = 1_000_000_007L;
    static final int MINV = 3500;
    static final int MAXV = 4500;
    static final int MASK = 8192;

    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    static boolean[] sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        if (n >= 1) isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (!isPrime[i]) continue;
            for (int j = i * i; j <= n; j += i) isPrime[j] = false;
        }
        return isPrime;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        boolean[] prime = sievePrimes(MASK - 1);

        int q = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (q-- > 0) {
            int n = fs.nextInt();
            int[] freq = new int[MAXV + 1];
            for (int i = 0; i < n; i++) freq[fs.nextInt()]++;

            long[] dp = new long[MASK];
            dp[0] = 1;

            for (int v = MINV; v <= MAXV; v++) {
                int c = freq[v];
                if (c == 0) continue;

                long evenWays = c / 2L + 1L;
                long oddWays = (c + 1L) / 2L;

                long[] ndp = new long[MASK];
                for (int x = 0; x < MASK; x++) {
                    long val = (dp[x] * evenWays + dp[x ^ v] * oddWays) % MOD;
                    ndp[x] = val;
                }
                dp = ndp;
            }

            long ans = 0;
            for (int x = 2; x < MASK; x++) {
                if (prime[x]) {
                    ans += dp[x];
                    if (ans >= MOD) ans -= MOD;
                }
            }

            out.append(ans).append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464617669

Link challenge: https://www.hackerrank.com/challenges/prime-xor/problem

Prime XOR