[BOJ 24731] 백준 24731번 - XOR-ABC
| 2022 연세대학교 신학기맞이 프로그래밍 경진대회 풀이 | ||
|---|---|---|
| A | [BOJ 24723] 녹색거탑 | |
| B | [BOJ 24724] 현대모비스와 함께하는 부품 관리 | |
| C | [BOJ 24725] 엠비티아이 | |
| D | [BOJ 24726] 미적분학 입문하기 2 | |
| E | [BOJ 24727] 인지융~ | |
| I | [BOJ 24731] XOR-ABC |
1. 문제
$24731$. XOR-ABC (2022 연세대학교 신학기맞이 프로그래밍 경진대회 I번)
2. 풀이
$1\leq A,B\leq 2^k-1$이고 $A\neq B$인 $A,B$에 대해서 $A\ xor\ B=C$를 생각해보자. (문제에서 $A\lt B$ 조건이 빠진 상태)
- 두 수를 $xor$하면, 그 결과값의 자릿수는 두 수의 최대 자릿수를 넘지 않는다.
A xor A = 0인데 $A\neq B$이므로, 결과값이 0이 나올 수 없다.
위 두 조건에 의해 결과값 $C$는 $1\leq C\leq 2^k-1$을 만족한다.
A xor 0 = A인데 $A\neq 0, B\neq 0$ 이므로, 결과값이 $A$ 또는 $B$가 나올 수 없다.
위 조건에 의해 결과값 $C$는 $C\neq A, C\neq B$를 만족한다.
따라서 문제의 조건을 만족하는 어떤 $A, B$를 고르더라도, 문제의 조건을 만족하는 결과값 $C$가 도출된다.
이제 $1\leq A,B,C\leq 2^k-1$이고 $A\neq B \neq C$인 $(A,B,C)$의 개수를 세는 문제로 바뀌었다.
$A$는 $2^k-1$개 가능하고, $B$는 $2^k-2$개 가능하다. $C$는 $A$와 $B$가 정해짐에 따라 결정된다. 따라서 총 경우의 수는 $(2^k-1)\times (2^k-2)$이다.
$A\lt B\lt C$인 $(A,B,C)$는 순서 없는 $3!=6$ 개의 $(A,B,C)$쌍에서 하나만 존재한다. 따라서 총 경우의 수를 $6$으로 나누어야 한다.
따라서 정답은 $\frac{(2^k-1)\times (2^k-2)}{6}$이다.
$2\leq K\leq 10^{18}$이므로, 그냥 계산하면 시간 내에 정답을 구할 수 없다. 아래의 두 가지 방법이 필요하다. (이 두 방법은 인터넷 검색을 통해 많은 자료를 찾을 수 있다.)
- 거듭제곱을 효율적으로 계산하기 위해
분할 정복을 이용한 거듭제곱을 사용한다. - 값을 나눈 나머지를 구하는데 수식에 분모가 존재하므로,
모듈로 곱셈 역원을 사용한다.
최종적으로 다음을 구하면 된다.
$((2^k-1)\times (2^k-2)\times 6^{MOD-2})\%MOD$
3. 채점 결과
4. 회고
나중에 알고보니 실제 대회에서 문제를 풀때 틀린 풀이로 접근했음에도 우연히 올바른 결론이 나와버렸다. 대회 종료 후, 풀이를 다시 완벽하게 정리하였다.
댓글남기기