Jzzhu and Numbers (CF 257D)

http://www.codeforces.com/problemset/problem/449/D

O(2^20 * N)

cnt[i] = (i를 서브마스크로 가지고 있는 Aj의 수) 라고 정의하자. 즉 수열 A에서 (Aj & i == i) 인 원소의 수이다. 이건 O(2^20 * N)에 계산 가능하다.

이제 답은 2 ^ cnt[0] 이.. 었으면 참 좋겠지만, 0이 아닌 다른 수를 서브마스크로 가지고 있는 Aj들이 존재하기 때문에 저럴 수는 없다. 고로 포함배제를 사용한다. 포함배제를 사용할때는, i의 비트의 수를 기준으로 포함 / 배제를 나눈다. i의 비트의 수가 홀수면 2 ^ cnt[i]를 빼주고, 아니면 2 ^ cnt[i]를 더해주는 식이다.

O(2^20 * 20 + N)

a[i] = (Aj == i인 j의 수) 라고 정의했을 때, cnt[]는 해당 비트의 서브마스크를 모두 순회하는 식으로 구할 수 있다. 이 부분을 dp (라고 하긴 살짝 애매한데) 로 처리해주는 게 풀이의 요지이다.

dp를 정의하자. dp[i][j] = 0 ~ i-1번째 비트가 j의 서브마스크이고, i ~ 19번째 비트는 정확히 j인 원소 수.

* dp[0]은 자명하다.

* dp[i][j]에서, j의 i-1번째 비트가 0일 경우에는, dp[i-1][j] + dp[i-1][j + 2^(i-1)]이 답이 된다. 아닐 경우에는 dp[i-1][j]가 답이 된다.

편의상 2차원 배열로 서술했지만 그냥 1차원 배열에 전파시킨다는 느낌으로 루프를 돌리면 더 편하다.

이 외에도 분할 정복 등의 방법으로 이를 해결할 수 있다. (http://hsin.hr/coci/archive/2011_2012/ contest #6 kosare 참고.)