백준 15710번: xor 게임

www.acmicpc.net/problem/15710

15710번: xor 게임

---

xor 연산에 대해 잘 모르면 해결하기 어려운 문제입니다.

 

먼저 몇 가지 예시를 통해 생각해봅시다.

 

예를 들어, $10111011_{\left( 2 \right)}$ 과 xor연산을 해서 $00000111_{\left( 2 \right)}$ 이 되는 수가 있을까요?

 

네, $10111100_{\left( 2 \right)}$ 이 바로 그런 숫자입니다.

 

그러면 $10111011_{\left( 2 \right)}$ 과 xor연산을 해서 $11100111_{\left( 2 \right)}$이 되는 수는 있을까요?

 

네, $01011100_{\left( 2 \right)}$ 이 바로 그런 숫자입니다.

 

비단 $10111011_{\left( 2 \right)}$ 뿐만이 그런게 아니라, 일반적으로 모든 $a,b$ 에 대해 $a$ xor $x$ $=$ $b$의 근 $x$가 항상 존재하고, 이 근은 유일합니다.

 

따라서 게임의 $N-1$번째 턴의 결과로 chogahui05가 가진 카드에 적힌 숫자가 $X$라고 한다면,

 

chogahui05는 $N$번째 턴에서 반드시 $X$와 xor연산하여 $b$가 나오는 값을 선택할 수 있습니다. ($X$와 $b$의 값에 상관없이!)

 

즉 게임의 과정에서 $N$번째 턴의 결과가 $b$가 되기 위해 고를 수 있는 카드는 반드시 한 개 존재하며

 

그 외의 턴에서 고를 수 있는 카드는 $2^{31}$개가 됩니다.

 

따라서 $N$이 주어졌을 때 $\left( 2^{31} \right)^{N-1}=2147483648^{N-1}$ 을 $\left(10^{9}+7\right)$로 나눈 나머지를 구해주면 해결되는 문제입니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#define mod 1000000007

long long power_modular (long long base, int power);

int main() {
	int a, b, n;
	scanf("%d %d %d", &a, &b, &n);
	printf("%lld", power_modular(2147483648ll, n-1));
	return 0;
}

long long power_modular (long long base, int power) {
	base %= mod;
	long long result = 1;
	while(power) {
		if (power % 2) {
			result = (result * base) % mod;
		}
		base = (base * base) % mod;
		power /= 2;
	}
	return result;
}

 

(C11, 1116KB, 0ms, 제출번호 26406084)

---

$2147483648^{N-1}$ 을 $2^{31\times \left( N-1 \right)}$ 으로 해석하여 구할 수도 있습니다.

 

다만 그 경우엔 power에 들어갈 값이 int범위를 초과할 수 있어 long long으로 바꿔주어야합니다.

 

글쓰고 있는 시점에서 적용중인 코드 하이라이팅 스크립트에서 2147483648에 postfix로 붙인 LL을 감지 못하고 있습니다만,

 

2147483648이 long long임을 나타내기 위해 postfix로 LL을 붙여주었습니다.

 

modulo가 소수이고 $N\leq 10^{9}+7$이므로 base자리에 2를 넣고 페르마의 소정리를 써서

 

power자리에 $31\times \left( N-1 \right)$을 $\left(10^{9}+6 \right)$으로 나눈 값을 넣어도 될 것 같습니다.