[백준] 24731. XOR-ABC

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

문제요약

• A < B < C을 만족하며 A xor B = C인 쌍의 개수 구하기
• K자리 이진수, K = 10^18
• 공식해설 은 여기 있고, 방향이 다름)

접근법

• K가 작으면 완전탐색으로 하면 되겠지만.
• A, B 특징이 있음
• 특징 1
  • A, B 상위비트가 동일하면 xor 결과가 0이 나옴. 그런데 비트가 하나라도 1이 있으면 안됨.
  • 0010... xor 0010... = 0000... => C가 가장 작아짐
  • 0000... xor 0000... = 0000... => 나쁘지 않음
• 특징 2
  • A, B 어느순간 달라지는 시점이 나타날텐데, 달라질때 B쪽이 1이어야함
  • 000... xor 001... = 001... => 나쁘지 않음
  • 001... xor 000... = 001... => A > B가 됨
• 특징 3
  • C가 더 커지려면 B보다 큰 뭔가가 있어야함 => B가 0일때 C가 1인 순간이 나타나야함 => A 가 1이면서 B가 0인 순간이 나타나야함 => 특징 2 이후에 나타나야함
  • 000...1... xor 001...0... = 001...1... => 일단 A<B는 만족하고 중간을 적절하게 하면 C가 작지는 않을 것이고, A에 1, B에 0이 나타나는 순간부터 C가 커질 것임
• 특징 4
  • 특징 3의 중간은 어느 순간 C가 커지기 전까지 B와 크기가 같아야함
  • 특징 3의 중간을 적절하게 하는 방법을 생각해보면 일단 B보다 작아서는 안됨 => B가 0일때 0, 1일때 1은 나와야함
  • A/B 조합을 생각해보면 0/0, 0/1 이 가능함
• 특징 5
  • 수열의 모양이 특징1 | 특징2 | 특징3 | 특징4 | 가 되고 나서부터 이후는 아무렇게나 나와도 됨.
  • A=B=C를 유지하다가(특징1), A < B = C 발생(특징2), A < B = C 유지(특징3), A < B < C 발생(특징4), 이후 아무렇게(A, B에 맞추어 C를 만들면 됨)
• 지금까지 생각한 특징을 구조화 시킬 수 있음. A, B 입장에서 설명하면
  • {0/0이 나오는 구간} {0/1발생} {0/0, 0/1이 나오는 구간} {1/0 발생} {모든 경우의 수가 나오는 구간}
  • {0/1발생}, {1/0 발생} : 특정 위치의 경우의 수 가능
  • {0/0, 0/1이 나오는 구간} : 길이에 따라 ${2^x}$ 경우의 수
  • {모든 경우의 수가 나오는 구간} : 길이에 따라 ${4^i}$ 경우의 수
  • i가 정해지면 x의 범위는 0 ~ K - 1 - 1 - i가 됨 : ${4^i \times ({2^0 + 2^1 + ... + 2^{k-2-i}}) = 4^i \times (2^{k-1-i} - 1)}$
  • i의 값은 0 ~ k-2까지임(0/1 발생, 1/0발생 위치는 빼야하니까)
  • ${\sum_{i=0}^{k-2} {4^i \times (2^{k-1-i} - 1)}}$
• 그런데 식을 전개해보면 앞부분/뒷부분으로 나눠짐
  • ${\sum_{i=0}^{k-2} {4^i \times (2^{k-1-i})} - \sum_{i=0}^{k-2} {4^i}}$
  • 앞부분에 ${4^i}$를 정리하면 ${\sum_{i=0}^{k-2} { 2^{k-1+i}} = {2^{k-1}}\sum_{i=0}^{k-2} { 2^i}}$
  • 등비수열 합 공식으로 계산이 가능하고, 뒷부분은 3의 모듈러 역원을 이용하면 됨

다른 접근법

• 조합???
• DP 식이 유도되는 것 같음
• Berlekamp-Massey 알고리즘 용어가 나옴???