पायथन में दी गई संख्याओं की सूची के लिए सभी क्वेरी के लिए kpr योग खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। हमारे पास queries नामक क्वेरी की एक सूची भी है जहां queries[i] में तीन एलिमेंट [k, p, r] होते हैं, प्रत्येक क्वेरी के लिए हमें kpr_sum ढूंढना होगा। kpr_sum का सूत्र नीचे दिया गया है।

$$\mathrm{kpr\_sum = \sum_{i=P}^{R-1}\sum_{j=i+1}^{R}(K \oplus (A[i] \oplus A[j])))}$$

यदि योग बहुत बड़ा है, तो योग को 10^9+7 मॉड्यूलो वापस करें।

उदाहरण के लिए, यदि इनपुट nums = [1,2,3], queries = [[1,1,3],[2,1,3]] है, तो आउटपुट [5, 4] होगा क्योंकि पहले एलिमेंट के लिए यह (1 XOR (1 XOR 2)) + (1 XOR (1 XOR 3)) + (1 XOR (2 XOR 3)) = 5 है, इसी तरह दूसरी क्वेरी के लिए यह 4 है।

हल करने के चरण

1. m := 10^9 + 7
2. N := len(nums)
3. q_cnt := len(queries)
4. C := एक नई सूची
5. res := एक नई सूची
6. i को 0 से 19 तक लूप चलाएं:
   • R := एकल एलिमेंट 0 वाला ऐरे
   • t := 0
   • nums में प्रत्येक x के लिए:
     • t := t + ((x >> i) & 1)
     • t को R के अंत में जोड़ें
   • R को C के अंत में जोड़ें
7. j को 0 से q_cnt तक लूप चलाएं:
   • (K, P, R) := queries[j]
   • d := R - P + 1
   • t := 0
   • i को 0 से 19 तक लूप चलाएं:
     • n1 := C[i][R] - C[i][P-1]
     • n0 := d - n1
     • यदि (K >> i) & 1 नॉन-जीरो है, तो:
       • x := (n1 * (n1 - 1) + n0 * (n0 - 1)) >> 1
     • अन्यथा:
       • x := n1 * n0
     • t := (t + (x << i)) % m
   • t को res के अंत में जोड़ें
8. res वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(nums, queries):
    m = 10**9 + 7
    N = len(nums)
    q_cnt = len(queries)
    C = []
    res = []
    for i in range(20):
        R = [0]
        t = 0
        for x in nums:
            t += (x >> i) & 1
            R.append(t)
        C.append(R)
    for j in range(q_cnt):
        K, P, R = queries[j]
        d = R - P + 1
        t = 0
        for i in range(20):
            n1 = C[i][R] - C[i][P-1]
            n0 = d - n1
            if (K >> i) & 1:
                x = (n1 * (n1 - 1) + n0 * (n0 - 1)) >> 1
            else:
                x = n1 * n0
            t = (t + (x << i)) % m
        res.append(t)
    return res

nums = [1,2,3]
queries = [[1,1,3],[2,1,3]]
print(solve(nums, queries))

इनपुट

[1,2,3], [[1,1,3],[2,1,3]]

आउटपुट

[5, 4]