We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Prime XOR
  5. Discussions

Prime XOR

Sort by

recency

|

51 Discussions

|

  • Tusenka
     + 0 comments

    For multiset there would be infinit sets, am I right? Lets b - prime. Then Example: a^a=0 0^b=b {b} a^a^b=b {a, a, b} The example is wrong

  • vladalx
     + 0 comments

    Since what is required is a MULTISET ( can contain duplicates ) that can be formed from the elements of the initial array ( not specified that should only be used once, meaning an element can be selected multiple times for a multiset ), then the result is : an infinite number of multisets. If the elements should only be used once, then what is the reason for the MULTISET specification ?

  • zoyashah41306
     + 0 comments

    Prime XOR is a fascinating concept in computer science and cryptography, involving the exclusive OR (XOR) operation applied to prime numbers. This technique leverages the unique properties of prime numbers to enhance data security and encryption methods. As developers and researchers explore Prime XOR, they uncover new potentials for creating robust encryption algorithms that safeguard information against unauthorized access. Printed tote bags featuring the Prime XOR theme become popular among enthusiasts, symbolizing their passion for cutting-edge technology and cryptographic advancements. These bags not only serve a practical purpose but also inspire conversations about the future of digital security and innovation.

  • dehaka
     + 0 comments
    long primeXor(vector<int> arr) {
    vector<bool> prime(8192, true);
    prime[0] = false, prime[1] = false;
    for (int p = 2; p*p <= 8191; p++) {
        if (prime[p] == true) {
            for (int i = p*p; i <= 8191; i += p)
                prime[i] = false;
        }
    }
    long total = 0, mod = 1000000007;
    vector<long> counter(8192);
    vector<int> dupe(4501), unique;
    for (int i=0; i < arr.size(); i++) {
        if (dupe[arr[i]] == 0) unique.push_back(arr[i]);
        dupe[arr[i]]++;
    }
    counter[0] = 1;
    for (int i=0; i < unique.size(); i++) {
        vector<long> temporary = counter;
        int F = dupe[unique[i]]/2;
        for (int j=0; j < 8192; j++) {
            int K = unique[i]^j;
            counter[j] = (counter[j] + temporary[j]*F) % mod;
            if (dupe[unique[i]] % 2 == 0) {
                counter[K] = (counter[K] + temporary[j]*F) % mod;
            } else {
                counter[K] = (counter[K] + temporary[j]*(F+1)) % mod;
            }
        }
    }
    for (int i=0; i < counter.size(); i++) {
        if (prime[i]) total = (total + counter[i]) % mod;
    }
    return total;
}

  • alexey_shayakhm1
     + 0 comments

    C++ solution

    int primeXor(vector<int> a)
{
    const int MOD = 1000000007, MAX_XOR = 8192,
        MIN_VALUE = 3500, MAX_VALUE = 4500;
    int valueCount[MAX_VALUE - MIN_VALUE + 1], 
        xorCount[MAX_XOR], delta[MAX_XOR]; 
    int i = 0, j = 0;        
    memset(valueCount, 0, sizeof(valueCount));
    memset(xorCount, 0, sizeof(xorCount));    
    for (auto v : a) valueCount[v - MIN_VALUE]++;
    xorCount[0] = 1;
    for (int v = MIN_VALUE, vi = 0; v <= MAX_VALUE; v++, vi++) {
        if (!valueCount[vi]) continue;        
        memset(delta, 0, sizeof(delta));
        int odd = (valueCount[vi] + 1) / 2;
        int even = valueCount[vi] / 2;
        for (i = 0; i < MAX_XOR; i++) {
            if(odd) delta[i ^ v] = 
                (delta[i^v] + int64_t(xorCount[i]) * odd) % MOD;
            if(even) delta[i] = 
                (delta[i] + int64_t(xorCount[i]) * even) % MOD;
        }
        for(i = 0; i < MAX_XOR; i++) 
            if(delta[i]) 
                xorCount[i] = (xorCount[i] + delta[i]) % MOD;
    }    
    int result = 0;                
    vector<int> numbers(MAX_XOR); 
    for (i = 2; i < MAX_XOR; i++)
        for (j = i * i; j < MAX_XOR; j += i)
            numbers[j] = 1;
    for (i = 2; i < MAX_XOR; i++)
        if (!numbers[i] && xorCount[i])
            result = (result + xorCount[i]) % MOD;
    return result;
}