BOJ 34905 Quantum Beaver

이 문제는 비트 트라이에 세그먼트 트리를 얹어서 풀 수 있습니다.

$N = 1$인 경우의 문제를 풀 수 있고 각각의 $d_i$를 넣고 빼는 쿼리를 처리할 수 있다면, 문제가 요구하는 식에서 합의 순서를 바꿔 1번째 원소가 가질 수 있는 가능한 모든 수의 합, …, $N$번째 원소가 가질 수 있는 가능한 모든 수의 합을 구해서 문제를 풀 수 있을 것입니다.

배열에서 어떤 자리가 최종적으로 $c_i$가 되는 경우의 수는 다음과 같이 구해집니다.

• $d_j$들 중에서 $K-1$번째 비트가 $c_i$와 다른 것이 있다면, 그 비트는 XOR 결과 1이 되어야 하므로 전체 경우의 수가 절반으로 나눠집니다.
• 그러한 것이 없다면 전체 경우의 수는 그대로 다음 비트로 전파됩니다. 이는 역으로 생각하면 그 비트를 제외한 $2^{K-1}$가지 중에서 계산한 경우의 수에 2배를 한 것과 같습니다.
• 트라이를 따라가면서 이 과정을 반복합니다.

일단 $d_i$의 목록이 사전에 정해져 있으므로 이들 값을 모두 포함하는 트라이를 만들고, 각 노드에 대해 그 노드에서 도달할 수 있는 리프 중에서 현재 켜져 있는 $d_i$의 개수를 저장합니다. 그러면 각 노드에서 그 노드 아래의 리프들이 총합에 기여하는 값을 세그먼트 트리와 같은 방식으로 구할 수 있습니다.

• 리프에는 $c_i$를 저장합니다.
• 어떤 노드의 자식이 두 개이고 그 둘이 모두 비어 있지 않다면, 양쪽의 값을 더해 줍니다.
• 둘 중 한 쪽이 비어있다면, 반대쪽 값을 2배 해서 저장합니다. 둘 다 비어있다면 이 노드의 값은 0입니다.
• 자식이 한 개라면 그 자식의 값을 2배 해서 저장합니다.

$d_i$를 하나 켜고 끄는 업데이트는 리프를 먼저 업데이트하고 루트 방향으로 따라가면서 모든 값을 업데이트해주면 됩니다. 이 업데이트를 이용해서 배열의 인덱스 방향으로 스위핑하여 각 인덱스에서의 총합을 모두 구하면 문제의 정답을 구할 수 있습니다.

이대로 구현 시 마지막 서브태스크에서 시간 초과를 받는다면, 연속으로 자식이 한 개인 구간들을 한 번에 건너뛸 수 있도록 추가 처리를 해주면 통과합니다.