멋진 수가 아닌 수의 개수를 DP로 세면 됩니다.

이진수 표현이 k자리이고 (최상위 비트는 1), 멋진 수가 아니면서, 최하위 2비트는 00, 01, 10, 11 중 b인 것의 개수를 DP[k][b]라고 놓고 점화식을 세워보시면 될 듯 싶습니다.

위 방법대로면 구간이 0 ~ 2^K-1 꼴일 때가 우선 풀립니다.

이제 L에서 R까지만 본다는 조건을 대응하려면, L에서 R까지를 2의 거듭제곱 기준으로 세그먼트 트리 구간 분할하듯이 분할해서 Lazy propagation 할 때 커버되는 구간들을 수거하여 각각을 카운팅하면 됩니다. 각 부분문제는 구간이 0 ~ 2^K-1 꼴일 때와 유사하기 때문입니다.

조언감사합니다 :) 제가 더 생각해보겠습니다-! 허허