알고리즘 : 범위 내의 숫자의 제한된 XOR

Question

숫자 n이 주어 졌다고합시다. [L, R] 범위에있는 값의 수 S^(S + n)을 찾아야합니다. (여기서 S는 음이 아닌 정수이고 ^는 비트 xor 연산자입니다.) n은 두 가지의 전원이 (그들은 매우 유용한 패턴이)

내가 어떤 일반적인 N에 대해이 문제를 해결하는 방법을 잘 모르겠습니다 경우

나는 쉽게이 작업을 수행 할 수 있습니다. 제안 사항이 있으십니까?

EDIT :

N은 음이 아닌 정수이다. n, L, R은 모두 10^18보다 작습니다.

이것은 언젠가 되돌려 주었던 연습 테스트에서 프로그래밍 질문이었습니다. 저는 StackOverflow에서 이와 비슷한 질문을 보았습니다.

편집 2 : 예와 함께 설명하면서는 는 N = 1 그런 다음 우리는 S가^(S + 1) 항상 모든 사람의 바이너리 표현을 가질 것이라는 점을 알고있다 말한다. 예 : 1,3,7, ...

이렇게 해결하는 것은 간단합니다. Range [L, R] 내에서 그러한 숫자의 수를 계산하면됩니다. 매우 간단합니다.

n = 2 인 경우 비슷한 방법으로 작동합니다. 그러나 n이 2의 거듭 제곱이 아니면 어떻게 해야할지 잘 모르겠다. 에 대해 S^(S + n)이라고 쓸 수있는 (무한한) 숫자를 C(n)이라고합시다.

Answer 1

우리가 세트 C(n)에 다음과 같은 점화식 :

• n = 2k 경우 다음도 C(n) = {2x : x in C(k)}이다;
• n = 2k + 1이 홀수이면 C(n) = {2x + 1 : x in C(k)} union {2x + 1 : x in C(k + 1)}입니다.

이러한 관계로부터 알고리즘을 추론 할 수 있습니다. 좀 더 정확히 말하자면 (C(n), C(n + 1)) 쌍은 (C(n/2), C(n/2 + 1))에서 추론 할 수 있습니다. C(n)의 모든 요소는 n과 동일한 패리티를 가지므로 과 C(k + 1)이 교차하지 않기 때문에 위의 union은 실제로는 분리 된 결합입니다. 재발 관계의

---

증명 :

단순히 n 및 S의 마지막 이진수 봐.