https://www.acmicpc.net/problem/30798
문제 요약
- xor해서 x가 되는 서로다른 n개의 숫자 구하기
- 0 <= x <= 2^30, 0 < 숫자 < 2^63, 4 <= n <= 10^6
접근법
- 기본적인 아이디어
- 1, 2, 3, 4, 5, ... 를 하고 마지막 숫자는 1^2^3^4^5 하기
- 1, 2, 3, 4, 5 연속으로 xor하면 주기적으로 0이 나옴
- 1, 2, 4, 8, 7, 15 처럼 한 비트씩만 사용하고 마지막 비트는 모든 비트를 사용하면 xor하면 0
- 마지막 숫자가 겹칠 수 있으므로 적절히(?) 변환
- 케이스를 나눠서 접근해본다.
- x가 0이 아닌 경우
- 1,2,3,4,5.... 와 1^2^3^... 를 준비하고 모두 31 bit shift
- 마지막 숫자에만 x를 더함(x < 2^30이기 때문에 비트가 안 겹침)
- x가 0인 경우
- 방금 사용한 방법을 적용을 못함(+ 0이라 효과가 없음)
- 연속숫자 xor 0 과 한비트씩 사용해서 0을 만드는 것을 혼합해서 적용
- 주기적으로 0을 이용 => 적절한 개수까지는 연속숫자를 이용해서 0이 나오게 만듬. 그리고 31bit shift
- 나머지 개수 한비트씩 사용해서 0을 만들도록 함 => 30개 정도는 커버 가능함
- 출력은 내림차순 정렬
- 0이 발생하지 않도록 주의
newbieski