투에-모스 수열

투에-모스 수열(Thue-Morse Sequence)은 0에서 시작하여, 매 단계마다 현재 수열의 보수(0↔1)를 뒤에 붙여 확장하는 이진 수열이다.

S₀ = 0
S₁ = 01
S₂ = 0110
S₃ = 01101001
S₄ = 0110100110010110

n번째(0-indexed) 원소 T(n)은 n의 이진 표현에서 1의 개수의 parity와 같다. 1의 개수가 짝수면 0, 홀수면 1이다.

n = 0  → 0   (이진: 0,    1의 개수: 0, 짝수) → T(0) = 0
n = 1  → 1   (이진: 1,    1의 개수: 1, 홀수) → T(1) = 1
n = 2  → 1   (이진: 10,   1의 개수: 1, 홀수) → T(2) = 1
n = 3  → 0   (이진: 11,   1의 개수: 2, 짝수) → T(3) = 0
n = 5  → 0   (이진: 101,  1의 개수: 2, 짝수) → T(5) = 0
n = 7  → 1   (이진: 111,  1의 개수: 3, 홀수) → T(7) = 1

증명

수열의 구성 방식에서 바로 유도된다.

길이 2^m인 수열 S_m이 있을 때, S_{m+1}은 S_m 뒤에 S_m의 보수를 붙인 것이다. 위치 n이 S_{m+1}의 후반부(n ≥ 2^m)에 있다면, 그 값은 전반부 위치 n - 2^m의 보수다.

T(n) = !T(n - 2^m)    (n ≥ 2^m일 때, 2^m은 n 이하의 가장 큰 2의 제곱수)

n의 최상위 비트가 1이면 보수를 한 번 취하고, 그 비트를 제거한 나머지에 대해 같은 논리를 반복한다. 결국 보수를 취한 횟수는 n의 이진 표현에서 1인 비트의 개수와 같고, 보수를 짝수 번 취하면 원래 값(0), 홀수 번이면 뒤집힌 값(1)이 된다.

구현

C++에서는 __builtin_parityll로 한 줄에 구할 수 있다. 이 함수는 인자의 이진 표현에서 1의 개수가 홀수면 1, 짝수면 0을 반환한다.

// 1-indexed k번째 원소
cout << __builtin_parityll(k - 1);

재귀로 구현할 수도 있다. k보다 작은 가장 큰 2의 제곱수 p를 구해서 !f(k-p)로 재귀한다.

int f(long long k) {
    if (k == 1) return 0;
    long long p = 1LL << (63 - __builtin_clzll(k));
    if (p == k) p >>= 1;
    return !f(k - p);
}

---

참고

• https://www.acmicpc.net/problem/18222
• https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence