[백준 | Python] #23731 - XOR-ABC

 

24731번: XOR-ABC

 

문제

$K$자리 이진수 $A, B, C$가 $1\leq A<B<C\leq2^k-1$를 만족한다. 이때 $A \text{ xor } B = C$인 순서쌍 $(A,B,C)$의 개수를 구하시오.

 

아이디어

$K$가 1씩 커질 때마다 제곱 단위로 경우의 수가 늘어나므로 단순히 브루트포스로 풀 수는 없을 것이다.

따라서 문제를 해결할 수 있는 하나의 식 $f(K)$가 존재할 것이라 추측하였다.

 

혹시 알고 있는가? xor연산 $X \text{ xor } Y=Z$가 성립하면 $X, Y, Z$의 위치를 자유롭게 변경한 6개의 식 모두 항상 성립한다.

 

$$0\text{ xor }0=0$$

$$0\text{ xor }1=1$$

$$1\text{ xor }0=1$$

$$1\text{ xor }1=0$$

위 연산에서 0은 항상 홀수 개만큼 등장하는 것을 관찰해보면 쉽게 짐작할 수 있다.

 

이제 상상이 간단해진다.

문제의 조건을 만족하는 세 수의 순서쌍을 다음과 같이 간단하게 찾을 수 있다.

서로 같지 않은 두 수 $X$와 $Y$에 대해 $X\text{ xor }Y=Z$를 구하고 대소관계에 맞게 xor 식의 $X, Y, Z$를 변경해주면 된다.

 

예를 들어, $K=5$라고 가정하고 아무 두 수 $X=10101$과 $Y=11000$를 택하자. 이때

$$10101\text{ xor }11000=01101$$

이고 xor 연산의 성질을 이용해 순서를 적절히 변경하면

$$01101\text{ xor }10101=11000$$

를 얻는다.

 

결국 모든 경우의 수를 구하기 위해 $K$-bit이고 0이 아닌 서로 다른 두 수를 선택하는 경우의 수를 6으로 나누어 주기만 하면 된다!

$$f(K)=\frac{(2^k-1)\times (2^k-2)}{6}$$

 

구현

숫자를 입력 받고, 위 식을 계산하여 1000003으로 나눈 나머지만 구하면 된다.

 

문제는 거듭제곱의 지수부분이 너무 크다는 것인데 이는 분할정복을 통해 계산하여야 한다.

분할정복을 이용한 거듭제곱은 흔한 주제이니 설명은 따로 않겠다.

또한 이 과정에서 모듈러 연산에 대한 성질이 사용되는데 이 또한 흔한 주제이니 궁금하면 다른 곳을 참고해보자.

 

다행히 파이썬은 내장함수를 통해 이러한 과정을 어렵지 않게 수행할 수 있다.

 

코드

M = 1000003
k = int(input())
temp = pow(2, k, M)
print((temp-1)*(temp-2) // 6 % M)

 

숏코딩

숏코딩도 해보았다. 52Bytes.

t=pow(2,int(input()),m:=6000018)-1
print(~-t*t%m//6)

 

 

 

번외: $f(K)$의 다른 유도 방법

등비수열 합을 이용해서 f(K)를 구할 수도 있다. 궁금하면 펼쳐보자.

$A<B<C$를 만족하는 조건을 찾아보자.

$C$는 $A$와 $B$에 의해 자동적으로 결정되므로 언급을 생략한다.

 

1. $A$와 $B$의 최상위 비트가 (1, 1)이나 (1, 0)일 수는 없다.
2. $A$와 $B$의 최상위 비트가 (0, 0)인 경우 ($A$와 $B$의 대소관계가 확정되지 않음)
    하위 비트에서 (0, 1)이 등장할 때까지 (0, 0)이 얼마든지 등장할 수 있다.

    (1, 1)이나 (1, 0)은 아직 등장할 수 없다.

3. $A$와 $B$의 최상위 비트가 (0, 1)인 경우 ($A$와 $B$의 대소관계 확정)
    (1, 0)이 등장하여 $B$와 $C$의 대소관계가 확정되면 그 하위 비트로는 아무 조합이나 가능하다.
    (0, 0)이나 (0, 1)의 등장은 계속 가능하고 (1, 1)은 등장할 수 없다.

 

정리하면, 최상위비트부터

(0, 0)은 0개 이상 등장

(0, 1)이 등장

(0, 0)이나 (0, 1)이 0개 이상 등장

(1, 0)이 등장

아무 조합이 0개 이상 등장

 

따라서 총 $K$ 비트일 때 최상위 비트부터 1번째 비트라 하면 가능한 경우의 수는 다음과 같이 계산할 수 있다.

 

$1\leq X\leq K-1$인 $X$에 대해,

$X$번째 비트에 (0, 1), $X+1$번째 비트에 (1, 0)이 등장했다고 하면 가능한 경우의 수는 $4^{K-2-(X-1)}$

$X$번째 비트에 (0, 1), $X+2$번째 비트에 (1, 0)이 등장했하고 하면 가능한 경우의 수는 $2^1\times 4^{K-3-(X-1)}$

...

$X$번째 비트에 (0, 1), $K$번째 비트에 (1, 0)이 등장했다고 하면 가능한 경우의 수는 $2^{K-2-(X-1)}$

 

모든 $X$에 대해 이를 모두 더하는 식을 계산하여도 같은 $f(K)$를 구할 수 있다.