숫자 num의 목록이 있다고 가정합니다. 또한 쿼리[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입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- m :=10^9 + 7
- N :=숫자 크기
- q_cnt :=쿼리 크기
- C :=새 목록
- res :=새 목록
- 0에서 19 사이의 i에 대해 다음을 수행합니다.
- R :=단일 요소가 0인 배열
- t :=0
- 숫자 단위의 각 x에 대해 다음을 수행합니다.
- t :=t + (i번 오른쪽으로 이동한 후 x) AND 1
- R 끝에 t 삽입
- C 끝에 R 삽입
- 0에서 q_cnt 범위의 j에 대해 다음을 수행합니다.
- (K, P, R) :=쿼리[j]
- d :=R - P + 1
- t :=0
- 0에서 19 사이의 i에 대해 다음을 수행합니다.
- n1 :=C[i, R] - C[i, P-1]
- n0 :=d - n1
- if (i 번 오른쪽으로 이동한 후 K) AND 1이 0이 아닌 경우
- x :=(n1 *(n1 - 1) + n0 *(n0 - 1))/2의 몫
- 그렇지 않으면
- x :=n1 * n0
- t :=(t +(i번 왼쪽으로 이동한 후 x)) 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]