유사 칸토어 비트열

https://school.programmers.co.kr/learn/courses/30/lessons/148652

public class Solution {
    public static long solution(int n, long l, long r) {
        long length = (long) Math.pow(5, n);
        return countOnes(n, l - 1, r - 1, length);
    }
    
    public static long countOnes(int n, long start, long end, long len) {
        if (start >= len || end < 0) {
            return 0;
        }

        if (n == 0) {
            return (start < 1 && end >= 0) ? 1 : 0;
        }

        long subLen = len / 5;
        long sum = 0;

        // 첫 번째 구간 1(0~subLen-1)
        sum += countOnes(n - 1, start, end, subLen);
        
        // 두 번째 구간 1(subLen~2*subLen-1)
        sum += countOnes(n - 1, start - subLen, end - subLen, subLen);

        // 세 번째 구간 0(2*subLen~3*subLen-1), count = 0
        
        // 네 번째 구간 1(3*subLen~4*subLen-1)
        sum += countOnes(n - 1, start - 3 * subLen, end - 3 * subLen, subLen);

        // 다섯 번째 구간 1(4*subLen~5*subLen-1)
        sum += countOnes(n - 1, start - 4 * subLen, end - 4 * subLen, subLen);

        return sum;
    }
}