สมมติว่าเรามีรายการตัวเลข นอกจากนี้เรายังมีรายการข้อความค้นหาที่การสืบค้นข้อมูล[i] ประกอบด้วยสามองค์ประกอบ [k, p, r] สำหรับแต่ละข้อความค้นหา เราจะต้องหา kpr_sum สูตรสำหรับ kpr_sum มีดังนี้
$$\mathrm{{𝑘𝑝𝑟}\_{𝑠𝑢𝑚} =\sum_{\substack{𝑖=𝑃}}^{𝑅−1}\sum_{\substack{𝑗=𝑖+1}}^{𝑅}(𝐾 ⊕(𝐴[𝑖]⊕𝐴[𝑗]))}$$
หากผลรวมมากเกินไป ให้ส่งคืนผลรวมโมดูโล 10^9+7
ดังนั้นหากอินพุตเป็นเหมือน nums =[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 :=ขนาดของ nums
- q_cnt :=ขนาดของข้อความค้นหา
- C :=รายการใหม่
- res :=รายการใหม่
- สำหรับฉันในช่วง 0 ถึง 19 ให้ทำ
- R :=อาร์เรย์ที่มีองค์ประกอบเดี่ยว 0
- t :=0
- สำหรับแต่ละ x เป็น nums ทำ
- t :=t + (x หลังจากขยับ i ครั้งไปทางขวา) และ 1
- ใส่ t ต่อท้าย R
- แทรก R ที่ส่วนท้ายของ C
- สำหรับ j ในช่วง 0 ถึง q_cnt ทำ
- (K, P, R) :=แบบสอบถาม[j]
- d :=R - P + 1
- t :=0
- สำหรับฉันในช่วง 0 ถึง 19 ให้ทำ
- n1 :=C[i, R] - C[i, P-1]
- n0 :=d - n1
- ถ้า (K หลังจากเลื่อน i ครั้งไปทางขวา) และ 1 ไม่ใช่ศูนย์ แล้ว
- x :=ผลหารของ (n1 *(n1 - 1) + n0 *(n0 - 1))/2
- มิฉะนั้น
- x :=n1 * n0
- t :=(t +(x หลังจากขยับ i ครั้งไปทางซ้าย)) mod m
- ใส่ t ต่อท้าย 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]
