나머지 숫자의 xor가 0인 부분 집합의 수를 찾습니다. (Find number of subsets, that xor of remaining numbers equals to 0)

문제 설명

나머지 숫자의 xor가 0인 부분 집합의 수를 찾습니다. (Find number of subsets, that xor of remaining numbers equals to 0)

n개의 숫자가 주어졌을 때, 나머지 숫자 중 0과 같은 부분집합의 최소 수를 찾으십시오. 예:

{1,1,3,4,5}

결과는 3과 같습니다. 왜냐하면 하위 집합 {1,3}(두 가지 방법으로) 또는 {3,4,5}을 삭제할 수 있기 때문입니다.

O( 2^n) 무차별 대입.

참조 솔루션

방법 1:

Let us consider a Dynamic Programming table of size n*m where m=10^4. We have an array of size n, such that 1 <= a[i] <= m.

Now, D[i][j] = number of subsets such that xor of the set is j Here xor of the set means xor of all elements of set.

D[i][j] = D[i‑1][j] + D[i‑1][j xor a[i]]. This recursive relation can be derived from that fact that new element a[i] will be present in subset or not.

If a[i] is not present => any subset of i‑1 elements whose xor is j

If a[i] is present => any subset of i‑1 elements whose xor is j xor a[i].( Because j xor a[i] xor a[i] = j)

In this way you are able to find all the subset whose xor is any given number. Note that this given number can be only as large as m. Coming to your question, it just boils down to finding out subset of elements whose xor is X, where X is xor of all elements.

Time : O(nm)

(by Steve Madden、Rishit Sanmukhani)

참조 문서

1. Find number of subsets, that xor of remaining numbers equals to 0 (CC BY‑SA 2.5/3.0/4.0)