취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24731번 문제인 XOR-ABC이다.
문제는 아래 링크를 확인하자.

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

1 이상 $2^K-1$ 이하의 서로 다른 두 정수 $A$와 $B$를 골랐을 때, $A$와 $B$를 xor연산해 얻을 수 있는 정수 $C$는 $A$와 $B$와는 항상 다른 값인 1 이상 $2^K-1$ 이하의 정수가 된다는 점을 관찰하자. 그리고 이 세 수를 크기순으로 정렬해 나타내면 이는 문제에서 찾는 하나의 쌍이 됨을 확인하자.

이와 같은 구성의 세 수를 얻는 방법은 두 정수를 $A$와 $B$, $B$와 $A$, $A$와 $C$, $C$와 $A$, $B$와 $C$, $C$와 $B$와 같이 고르는 6가지가 존재한다. 이를 이용해 정수를 고르는 경우의 수를 얻을 수 있는 식을 세워 문제를 해결하자.

답을 주어진 소수로 나눈 나머지를 구하면 되므로 필요하면 모듈로 곱셈 역원을 이용해 나눗셈 연산을 진행하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll K;
ll x = 1, b = 2;
ll A, B;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K;
	while (K) {
		if (K & 1) {
			x = x * b % 1000003;
		}
		b = b * b % 1000003;
		K >>= 1;
	}
	A = x - 1, B = x - 2;
	if (A < 0) A += 1000003;
	if (B < 0) B += 1000003;
	cout << A * B * 833336 % 1000003;
}