링크

문제 요약

두 수열 A, B가 주어질 때 아래 두 값을 구하여라.

$ \displaystyle \sum_{i=1}^N\sum_{j=1}^N (A_i \And{} B_j) \pmod{1999} $
모든 $i, j$ 에 대하여 $(A_i+B_j)$ 의 bitwise and 연산 값

관찰

구해야 할 첫번째 값을 구하는 과정은 그리 어렵지 않다. 각 비트가 켜진 횟수가 총 몇번인지를 알면 바로 계산할 수 있기 때문이다. & 연산의 특성상 두 비트가 모두 켜져야 1이 나오므로, 각 배열에서 해당 비트가 켜진 개수가 중요한 정보이다. 따라서 아래와 같은 값을 계산하면 첫번째 값을 구할 수 있다.

$C_A(i)=$ 배열 A의 원소중 $i$ 번째 비트가 켜진 원소의 개수
$C_B(i)=$ 배열 B의 원소중 $i$ 번째 비트가 켜진 원소의 개수
$\displaystyle \sum_{i=0}^{28} (2^{i}\times{}C_A(i)C_B(i)) \pmod{1999}$

두번째 값을 구할 때 중요한 포인트는 해당 값에서 $i$번째 비트가 켜지기 위해서는 모든 합에 대하여 $i$번째 비트가 켜져있어야 한다는 것이다. 즉, 1개라도 해당 비트가 꺼져있다면 두번째 계산값에서 $i$번째 비트는 절대로 켜져있을 수 없다. 따라서 경우의 수를 나누어 분석해보도록 하자. 어떤 두 수 $A_i$ 와 $B_j$ 가 더해질 때 두 수의 $i$번째 비트의 켜짐 여부로 분류를 하면 아래와 같다.

$A_i$와 $B_i$의 $i$번째 비트의 상태가 같음 (둘 다 켜지거나 꺼짐)
이 경우는 $A_i$와 $B_i$의 단순히 $i$번째 비트끼리 더하면 해당 비트가 0이 나오므로, 각각의 0번째 ~ $(i-1)$번째 비트 부분을 더한 결과물이 $i$번째 비트를 켤 수 있어야 한다. 즉, 켜지 못하는 경우가 존재하면 해당 정답에서 해당 비트는 0이다.
$A_i$와 $B_i$의 $i$번째 비트의 상태가 서로 다름 (하나는 켜지고 하나는 꺼짐)
이 경우는 $A_i$와 $B_i$의 단순히 $i$번째 비트끼리 더하면 해당 비트가 1이 나오므로, 각각의 0번째 ~ $(i-1)$번째 비트 부분을 더한 결과물이 $i$번째 비트를 켤 수 없어야 한다. 즉, 켜는 경우가 존재하면 해당 정답에서 해당 비트는 0이다.

따라서 이 사실을 바탕으로 문제를 해결하면 된다. 첫번째 경우부터 생각을 해보면, 더해서 숫자가 가장 작은 경우를 확인해서 $i$번째 비트가 켜지는지 확인하면 된다. 왜냐하면 해당 경우가 $i$번 비트를 켠다면, 이보다 큰 값들을 더한 경우는 자명히 $i$번 비트를 켜기 때문이다. 반대로 두번째 경우는 더해서 숫자가 가장 작은 경우를 확인하여 $i$번 비트가 꺼져있는지 확인하면 된다. 이유는 첫번째 경우의 반대로 생각하면 자명하다.

풀이

풀이는 위의 관찰을 구현하면 바로 해결된다. 첫번째 값은 정말로 말 그대로 계산을 하면 되고, 다만 두번째 값의 경우는 실제로 구현할 때는 해당 비트가 꺼져있는 경우가 존재하는지 여부를 확인하는 것이 더 간편하다. 또한 두번째 값을 계산할 때는 0~28번째 비트 뿐만아니라 29번째 비트도 켜지는지 확인을 해야한다. 예를 들어 아래와 같은 입력은 두번째 계산값은 $2^{29}$ 이다.

1
268435456
268435456

따라서 첫번째 계산과 두번째 계산 모두 각 숫자를 비트별로 분석하여 전처리 하는 과정이 필요하므로 전처리에 $O(N\log{X})$ 의 시간이 걸리게 된다. 나머지 실질적 값 계산은 $O(\log{X})$ 에 가능하기 때문에 전체 시간 복잡도는 $O(N\log{X})$ 이다.