ধরুন আমাদের সংখ্যা সংখ্যার একটি তালিকা আছে। আমাদের কাছে প্রশ্নগুলির একটি তালিকাও রয়েছে যেখানে ক্যোয়ারী[i]-এ তিনটি উপাদান রয়েছে [k, p, r], প্রতিটি প্রশ্নের জন্য আমাদের kpr_sum খুঁজে বের করতে হবে। kpr_sum-এর সূত্র নিচের মত।
$$\mathrm{{𝑘𝑝𝑟}\_{𝑠𝑢𝑚} =\sum_{\substack{𝑖=𝑃}}^{𝑅−1}\sum_{\substack{𝑗=𝑖+1}}^{𝑅−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।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- m :=10^9 + 7
- N :=সংখ্যার আকার
- q_cnt :=প্রশ্নের আকার
- C :=একটি নতুন তালিকা
- res :=একটি নতুন তালিকা
- আমি 0 থেকে 19 রেঞ্জের জন্য, কর
- R :=একক উপাদান 0 সহ একটি অ্যারে
- t :=0
- সংখ্যায় প্রতিটি x এর জন্য, করুন
- t :=t + (x i বার ডানদিকে সরানোর পর) এবং 1
- R এর শেষে t ঢোকান
- C এর শেষে R ঢোকান
0 থেকে q_cnt রেঞ্জের মধ্যে j-এর জন্য - (K, P, R) :=প্রশ্ন[j]
- d :=R - P + 1
- t :=0
- আমি 0 থেকে 19 রেঞ্জের জন্য, কর
- 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 বাম দিকে বার করার পর)) মোড 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]
