Problem p02938 (python)

Fixed submission:

LARGE = 10 ** 9 + 7

# flag_x : left < x
# flag_y : y < right
# flag_z : msb


def f(pos, flag_x, flag_y, flag_z, memo, left, right):
    if pos == -1:
        return 1
    if memo[pos][flag_x][flag_y][flag_z] != -1:
        return memo[pos][flag_x][flag_y][flag_z]
    ret = 0
    # x 0, y 0
    if flag_x or left[pos] == '0':
        ret += f(pos - 1, flag_x, 1 if right[pos] == '1' else flag_y, flag_z, memo, left, right)
    # x 0, y 1
    if (flag_x or left[pos] == '0') and (flag_y or right[pos] == '1') and flag_z:
        ret += f(pos - 1, flag_x, flag_y, flag_z, memo, left, right)
    # x 1, y 1
    if flag_y or right[pos] == '1':
        ret += f(pos - 1, 1 if left[pos] == '0' else flag_x, flag_y, 1, memo, left, right)
    ret %= LARGE
    memo[pos][flag_x][flag_y][flag_z] = ret
    return ret


def solve_greed_f(L, R):

    res_g = 0

    for i in range(L, R + 1):
        for j in range(i, R + 1):
            if j % i == j ^ i:
                res_g += 1

    return res_g


def main():

    ll, rr = map(int, input().split())

    left = '{:060b}'.format(ll)[::-1]
    right = '{:060b}'.format(rr)[::-1]

    memo = [[[[-1 for m in range(2)] for k in range(2)] for j in range(2)] for i in range(60)]

    res = f(59, 0, 0, 0, memo, left, right)

    print(res)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):

LARGE = 10 ** 9 + 7

# flag_x : left < x
# flag_y : y < right
# flag_z : msb


def f(pos, flag_x, flag_y, flag_z, memo, left, right):
    if pos == -1:
        return 1
    if memo[pos][flag_x][flag_y][flag_z] != -1:
        return memo[pos][flag_x][flag_y][flag_z]
    ret = 0
    # x 0, y 0
    if flag_x or left[pos] == '0':
        ret += f(pos - 1, flag_x, 1 if right[pos] == '1' else flag_y, flag_z)
    # x 0, y 1
    if (flag_x or left[pos] == '0') and (flag_y or right[pos] == '1') and flag_z:
        ret += f(pos - 1, flag_x, flag_y, flag_z)
    # x 1, y 1
    if flag_y or right[pos] == '1':
        ret += f(pos - 1, 1 if left[pos] == '0' else flag_x, flag_y, 1)
    ret %= LARGE
    memo[pos][flag_x][flag_y][flag_z] = ret
    return ret


def solve_greed_f(L, R):

    res_g = 0

    for i in range(L, R + 1):
        for j in range(i, R + 1):
            if j % i == j ^ i:
                res_g += 1

    return res_g


def main():

    ll, rr = map(int, input().split())

    left = '{:060b}'.format(ll)[::-1]
    right = '{:060b}'.format(rr)[::-1]

    memo = [[[[-1 for m in range(2)] for k in range(2)] for j in range(2)] for i in range(60)]

    res = f(59, 0, 0, 0, memo, left, right)

    print(res)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
L, R = map(int, input().split())

LARGE = 10 ** 9 + 7


def get_l(vl, le_r):
    # vl <= L <= R <= 2 ** le_r - 1
    res_ = 0

    if vl == 0:
        res_ += pow(2, le_r, LARGE)
        vl = 1
    for l_ in range(le_r):
        if vl % (2 ** (l_ + 1)) != 0:
            le_total = le_r - bin(vl).count("1")
            res_ += pow(3, l_, LARGE) * pow(2, le_total - l_, LARGE)
            res_ %= LARGE
            vl += 2 ** l_
    return res_


def get_r(vr):
    # 0 <= L <= R <= vr
    if vr == 0:
        return 1
    elif vr == 1:
        return 2
    l_ = 0
    while True:
        if 2 ** (l_ + 1) - 1 > vr:
            break
        l_ += 1

    return (pow(3, l_, LARGE) + 2 * get_r(vr - 2 ** l_)) % LARGE


res = 0
le = 0
left = 2 ** le
right = 2 ** (le + 1) - 1


while True:
    if right < L:
        pass
    elif L < left < right < R:
        res += pow(3, le, LARGE)
    elif R < left:
        break
    elif left <= L <= right < R:
        res += get_l(L, le + 1)
    elif L < left <= R <= right:
        res += get_r(R - left)
    elif L < R:
        # left <= L <= R <= right:
        # find mid
        mid = left
        for le2 in range(le - 1, -1, -1):
            if L < mid + 2 ** le2 <= R:
                res += get_l(L - mid, le2)
                res += get_r(R - mid)
            elif mid + 2 ** le2 <= L:
                mid += 2 ** le2
            else:
                pass
    else:
        res = 1

    res %= LARGE
    le += 1
    left *= 2
    right *= 2
    right += 1

print(res)

Buggy submission (verdict: Runtime Error):
L, R = map(int, input().split())

LARGE = 10 ** 9 + 7


def get_l(vl, le_r):
    # vl <= L <= R <= 2 ** le_r - 1
    res_ = 0

    if vl == 0:
        res_ += pow(2, le_r, LARGE)
        vl = 1
    for l_ in range(le_r):
        if vl % (2 ** (l_ + 1)) != 0:
            le_total = le_r - bin(vl).count("1")
            res_ += pow(3, l_, LARGE) * pow(2, le_total - l_, LARGE)
            res_ %= LARGE
            vl += 2 ** l_
    return res_


def get_r(vr):
    # 0 <= L <= R <= vr
    if vr == 0:
        return 1
    elif vr == 1:
        return 2
    l_ = 0
    while True:
        if 2 ** (l_ + 1) - 1 > vr:
            break
        l_ += 1

    return (pow(3, l_, LARGE) + 2 * get_r(vr - 2 ** l_)) % LARGE


res = 0
le = 0
left = 2 ** le
right = 2 ** (le + 1) - 1


while True:
    if right < L:
        pass
    elif L <= left <= right <= R:
        res += pow(3, le, LARGE)
    elif R < left:
        break
    elif left <= L <= right <= R:
        res += get_l(L, le + 1)
    elif L <= left <= R <= right:
        res += get_r(R - left)
    else:
        # left <= L <= R <= right:
        # find mid
        mid = left
        for le2 in range(le - 1, -1, -1):
            if L < mid + 2 ** le2 <= R:
                res += get_l(L - mid, le2)
                res += get_r(R - mid)
            elif mid + 2 ** le2 <= L:
                mid += 2 ** le2
            else:
                pass

    res %= LARGE
    le += 1
    left *= 2
    right *= 2
    right += 1

print(res)

Buggy submission (verdict: Runtime Error):
L, R = map(int, input().split())

LARGE = 10 ** 9 + 7


def get_l(vl, le_r):
    # vl <= L <= R <= 2 ** le_r - 1
    res_ = 0

    if vl == 0:
        res_ += pow(2, le_r, LARGE)
        vl = 1
    for l_ in range(le_r):
        if vl % (2 ** (l_ + 1)) != 0:
            le_total = le_r - bin(vl).count("1")
            res_ += pow(3, l_, LARGE) * pow(2, le_total - l_, LARGE)
            res_ %= LARGE
            vl += 2 ** l_
    return res_


def get_r(vr):
    # 0 <= L <= R <= vr
    res_ = 0
    if vr == 0:
        return 1
    l_ = 0
    while True:
        if 2 ** (l_ + 1) - 1 > vr:
            break
        l_ += 1

    return (pow(3, l_, LARGE) + 2 * get_r(vr - 2 ** l_)) % LARGE


res = 0
le = 0
left = 2 ** le
right = 2 ** (le + 1) - 1


while True:
    if right < L:
        pass
    elif L <= left <= right <= R:
        res += pow(3, le, LARGE)
    elif R < left:
        break
    elif left <= L <= right <= R:
        res += get_l(L, le + 1)
    elif L <= left <= R <= right:
        res += get_r(R - left)
    else:
        # left <= L <= R <= right:
        # find mid
        mid = left
        for le2 in range(le - 1, -1, -1):
            if L < mid + 2 ** le2 <= R:
                res += get_l(L - mid, le2)
                res += get_r(R - mid)
            elif mid + 2 ** le2 <= L:
                mid += 2 ** le2
            else:
                pass

    res %= LARGE
    le += 1
    left *= 2
    right *= 2
    right += 1

print(res)