मान लीजिए कि हमारे पास संख्याओं की एक सूची है। हमारे पास प्रश्नों की एक सूची भी है जहां प्रश्नों [i] में तीन तत्व होते हैं [k, p, r], प्रत्येक प्रश्न के लिए हमें kpr_sum खोजना होगा। kpr_sum का सूत्र नीचे जैसा है।
$$\mathrm{{𝑘𝑝𝑟}\_{𝑠𝑢𝑚} =\sum_{\substack{𝑖=𝑃}}^{𝑅−1}\sum_{\substack{𝑗=𝑖+1}}^{𝑅}(𝐾 ⊕(𝐴[𝑖]⊕𝐴[𝑗]))}$$
अगर योग बहुत बड़ा है, तो योग मॉड्यूल 10^9+7 लौटाएं।
इसलिए, यदि इनपुट अंकों की तरह है =[1,2,3] प्रश्न =[[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 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- म :=10^9 + 7
- N :=अंकों का आकार
- q_cnt:=प्रश्नों का आकार
- सी :=एक नई सूची
- res :=एक नई सूची
- 0 से 19 की श्रेणी में i के लिए, करें
- R:=एकल तत्व 0 के साथ एक सरणी
- टी:=0
- अंकों में प्रत्येक x के लिए, करें
- t :=t + (x i बार दाईं ओर शिफ्ट होने के बाद) और 1
- आर के अंत में टी डालें
- C के अंत में R डालें
- जे के लिए 0 से q_cnt तक, करें
- (के, पी, आर):=प्रश्न [जे]
- d :=R - P + 1
- टी:=0
- 0 से 19 की श्रेणी में i के लिए, करें
- n1 :=C[i, R] - C[i, P-1]
- n0 :=d - n1
- यदि (i बार दाईं ओर शिफ्ट करने के बाद K) और 1 शून्य नहीं है, तो
- x :=(n1 *(n1 - 1) + n0 *(n0 - 1))/2 का भागफल
- अन्यथा,
- x :=n1 * n0
- t :=(t +(x i बार बाईं ओर शिफ्ट होने के बाद)) mod m
- res के अंत में t डालें
- रिटर्न रेस
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
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]