資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式，用於查詢給定數字列表中所有查詢的kpr和
假設我們有一個數字列表nums。我們還有一個查詢列表，其中queries[i]包含三個元素[k, p, r]，對於每個查詢，我們都必須找到kpr_sum。kpr_sum的公式如下所示。
$$\mathrm{{𝑘𝑝𝑟}\_{𝑠𝑢𝑚} =\sum_{\substack{𝑖=𝑃}}^{𝑅−1}\sum_{\substack{𝑗=𝑖+1}}^{𝑅}(𝐾 ⊕(𝐴[𝑖]⊕𝐴[𝑗]))}$$
如果和過大，則返回模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。
為了解決這個問題，我們將遵循以下步驟：
- m := 10^9 + 7
- N := nums的大小
- q_cnt := 查詢的數量
- C := 一個新的列表
- res := 一個新的列表
- 對於i從0到19，執行以下操作：
- R := 一個包含單個元素0的陣列
- t := 0
- 對於nums中的每個x，執行以下操作：
- t := t + (x右移i位) AND 1
- 將t插入到R的末尾
- 將R插入到C的末尾
- 對於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位) AND 1不為零，則：
- x := (n1 *(n1 - 1) + n0 *(n0 - 1))/2的商
- 否則：
- x := n1 * n0
- t :=(t +(x左移i位)) mod 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]
更新於：2021年10月6日
246次瀏覽
廣告