Soluție HackerRank pentru XOR love, subdomeniul Algebra, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: XOR love
  • Domeniu: Algebra
  • Limbaj: C++14

Challenge: XOR love

Subdomeniu: Algebra (algebra)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464755021

Limbaj: cpp14

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

Cerință

Devendra loves the XOR operation very much which is denoted by wedge sign in most of the programming languages. He has a list A of N numbers and he wants to know the answers of M queries. Each query will be denoted by three numbers i.e. K,P,R .

For query K,P text{ and } R, he has to print the value of the KPRsum which can be described as given below. As the value of the KPRsum can be large. So, print it modulus (10^9 + 7).

KPRsum = ∑_i=P^R-1 ∑_j=i+1^R (K oplus (A[i] oplus A[j]) )

Input Format
The first line contains an integer N, i.e., the number of the elements in the list. List is numbered from 1 to N.
Next line will contain N space seperated integers.
Third line will contain a number M i.e. number of queries followed by M lines each containing integers K,P & R.

Output Format
Print M lines, i-th line will be answer of i-th query. Answer will be 0 in case of P=R.

Constraints
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^6
1 ≤ M ≤ 10^5
0 ≤ K ≤ 10^6
1 ≤ P ≤ R ≤ N

Sample Input

3
1 2 3
2
1 1 3
2 1 3

Sample Output

5
4

Explanation

For first query, it will will be (1 oplus( 1 oplus 2) ) + (1 oplus( 1 oplus 3) ) + (1 oplus( 2 oplus 3) ) = 5

Cod sursă

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 1000000007LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    const int B = 31; // safe for values up to 1e9+
    vector<vector<int>> pref(B, vector<int>(n + 1, 0));
    for (int b = 0; b < B; ++b) {
        for (int i = 1; i <= n; ++i) {
            pref[b][i] = pref[b][i - 1] + ((a[i] >> b) & 1);
        }
    }

    vector<long long> pow2(B, 1);
    for (int b = 1; b < B; ++b) pow2[b] = (pow2[b - 1] * 2LL) % MOD;

    int q;
    cin >> q;
    while (q--) {
        int k, l, r;
        cin >> k >> l >> r;
        long long len = r - l + 1;

        long long ans = 0;
        for (int b = 0; b < B; ++b) {
            long long ones = pref[b][r] - pref[b][l - 1];
            long long zeros = len - ones;

            long long pairs_one;
            if (((k >> b) & 1) == 0) {
                // Need A[i]^A[j] bit = 1 -> different bits.
                pairs_one = ones * zeros;
            } else {
                // Need A[i]^A[j] bit = 0 -> same bits.
                pairs_one = ones * (ones - 1) / 2 + zeros * (zeros - 1) / 2;
            }

            long long contrib = (pairs_one % MOD) * pow2[b] % MOD;
            ans += contrib;
            if (ans >= MOD) ans -= MOD;
        }

        cout << ans % MOD << '\n';
    }

    return 0;
}
HackerRank Algebra – XOR love