আমাদের একটি নাম্বার লিস্ট আছে 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, এবং দ্বিতীয় কোয়ারীর জন্য ৪।
সমাধানের ধাপসমূহ (বিট ম্যানিপুলেশন + প্রিফিক্স সম)
m := 10^9 + 7N := nums-এর আকার,q_cnt := queries-এর আকারC := একটি নতুন লিস্টres := একটি নতুন লিস্টi= 0 থেকে ১৯ পর্যন্ত লুপ চালান (বিট পজিশন):R := [0]দিয়ে একটি অ্যারে শুরু করুনt := 0nums-এর প্রতিটিxএর জন্য:t += (x >> i) & 1R.append(t)
R-কেC-এ যোগ করুন
j= 0 থেকেq_cnt-1পর্যন্ত লুপ চালান:(K, P, R) := queries[j]d := R - P + 1t := 0i= 0 থেকে ১৯ পর্যন্ত লুপ চালান: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-এ যোগ করুন
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]
