배열 arr이 있다고 가정합니다. 합이 홀수인 부분배열의 수를 찾아야 합니다. 답이 너무 크면 10^9+7 모듈로 결과를 반환합니다.
따라서 입력이 arr =[8,3,7]과 같으면 모든 하위 배열이 [[8],[3],[7],[8,3],[3, 7],[8,3,7]] 이제 합 값은 [8,3,7,11,10,18]이므로 세 개의 홀수 합 값 [3,7,11]이 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
freq :=두 개의 요소 1과 0을 가진 목록
-
답변 :=0
-
접두사 :=0
-
arr의 각 x에 대해 수행
-
접두사 :=접두사 + x
-
ans :=ans + freq[1 XOR 접두어 AND 1]
-
freq[접두사 AND 1] :=freq[접두사 AND 1] + 1
-
-
모드로 반환(10^9+7)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(arr): freq = [1, 0] ans = prefix = 0 for x in arr: prefix += x ans += freq[1 ^ prefix&1] freq[prefix &s; 1] += 1 return ans % (10**9+7) arr = [8,3,7] print(solve(arr))
입력
[8,3,7]
출력
3