13169번: Xor of Sums

https://www.acmicpc.net/problem/13169

주어진 수열의 모든 부분합을 xor한 값을 구하는 문제이다.

단순히 부분합을 모두 구해서 풀면 $O(2^n)$의 시간복잡도가 걸리므로 TLE가 난다. 이런류의 문제에서는 주어진 수열을 절반씩 잘라 푸는 유명한 트릭이 있다. 모른다면 위키피디아 냅색 문제 문서의 meet in the middle에 잘 설명되어 있으니 참고하자.

수열을 반씩 잘라 구한 각 수열의 모든 부분합들의 집합을 u, v라 하자.
앞으로 답의 비트를 하나씩 결정시켜나갈 것이다. 답의 $2^i$ 자리는 각 부분합을 $2^i$으로 나눈 몫의 합이 홀수이면 1, 짝수이면 0이다.

u0 = u에서 $2^i$미만인 원소들 집합
t0 = t에서 $2^i$미만인 원소들 집합
n(A) = A의 원소 개수
f(i,A) = A의 원소들을 $2^i$으로 나눈 몫의 합

$2^i$ 자리를 결정하기 위해 따져봐야 조합은 다음과 같이 네 가지가 있다.
1. u-u0, t-t0의 조합
2. u0, t-t0의 조합
3. u-u0, t0의 조합
4. u0, t0의 조합

1번에서 만들어지는 수는 $2^i$으로 나눈 몫이 짝수이기 때문에 무시해도 된다.
2번에서 $2^i$으로 나눈 몫의 합은 n(u0) * f(i, t-t0)이다.
3번은 2번과 비슷하게 n(t0) * f(i, u-u0)이다.
4번에서는 합이 $2^i$이상인 조합의 수를 찾으면 된다. 이는 inchworm이나 binary search로 해결할 수 있다.(아래 소스에서는 binary search 사용)

이 네 가지 경우를 모두 계산하고 똑같은 방법으로 답의 모든 자리를 결정시킨다.

시간복잡도는 $O(nL*2^n)$ // L: 봐야하는 비트 수

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n;
long long r;
vector<long long> v[2] = { { 0 },{ 0 } };
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        int sz = v[i & 1].size();
        for (int j = 0; j < sz; j++) v[i & 1].push_back(v[i & 1][j] + x);
    }
    for (long long i = 1LL << 35; i >>= 1;) {
        int a = 0, b = 0;
        for (auto &it : v[0]) a += it / i & 1, it %= i;
        for (auto &it : v[1]) b += it / i & 1, it %= i;
        r = r << 1 | v[0].size() - a&b & 1 ^ v[1].size() - b&a & 1;
        sort(v[0].begin(), v[0].end());
        for (auto it : v[1]) r ^= v[0].end() - lower_bound(v[0].begin(), v[0].end(), i - it) & 1;
    }
    printf("%lld", r);
    return 0;
}