Problem:


Score : 600 points

Problem Statement

Given are integers L and R. Find the number, modulo 10^9 + 7, of pairs of integers (x, y) (L \leq x \leq y \leq R) such that the remainder when y is divided by x is equal to y \mbox{ XOR } x.

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

1 \leq L \leq R \leq 10^{18}

Input

Input is given from Standard Input in the following format:

L R

Output

Print the number of pairs of integers (x, y) (L \leq x \leq y \leq R) satisfying the condition, modulo 10^9 + 7.

Sample Input 1

2 3

Sample Output 1

3

Three pairs satisfy the condition: (2, 2), (2, 3), and (3, 3).

Sample Input 2

10 100

Sample Output 2

604

Sample Input 3

1 1000000000000000000

Sample Output 3

68038601

Be sure to compute the number modulo 10^9 + 7.



Sample input:
2 3


Sample output:
3

Submission status: Wrong Answer

Solution code:
L,R=map(int,input().split())
ans=0
mod=10**9+7
s=len(bin(R))-3
s=pow(2,s)-1
for i in range(L,s+1):
  a=bin(i)[2:]
  ans+=pow(2,a.count("0"),mod)
  ans%=mod
for i in range(s+1,R+1):
  for j in range(i,R+1):
    if j%i==j^i:
      ans+=1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
#y-x=y^x
L,R=map(int,input().split())
ans=0
mod=10**9+7
for i in range(L,R+1):
  a=bin(i)[:2]
  ans+=pow(2,a.count("0"),mod)
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
# L, R = map(lambda x: bin(int(x))[2:], input().split())
L_, R_ = map(lambda x: int(x), input().split())
L, R = bin(L_)[2:], bin(R_)[2:]
P = int(1e9+7)
n_pattern = [0] * (len(R))
n_pattern[0] = 1
for i in range(1, len(R)):
    n_pattern[i] = (3 * n_pattern[i - 1]) % P

ans = 0
for i in range(len(R)):
    ans = (ans + n_pattern[i]) % P

# xがL未満をひく
for i in range(len(L) - 1):
    ans = (ans - n_pattern[i]) % P
tmp = 1
for i, l in enumerate(L):
    if i == 0:
        continue
    elif l == '0':
        tmp *= 2
    elif l == '1':
        ans = (ans - tmp*2 * n_pattern[len(L) - i - 1])%P

# y がR以降を引く
tmp = 1
for i, r in enumerate(R):
    if i == 0:
        continue
    elif r == '1':
        tmp *= 2
    elif r == '0':
        ans = (ans - tmp*2 * n_pattern[len(R) - i - 1]) % P
print(ans)

def solve_naive(L, R):
    cnt = 0
    keta = len(bin(R)[2:])
    for x in range(1, pow(2, keta)):
        for y in range(x, pow(2, keta)):
            cnt += ((y % x) == (x ^ y))
    print(cnt)
    for x in range(1, L):
        for y in range(x, pow(2, keta)):
            cnt -= ((y % x) == (x ^ y))
    print(cnt)
    for x in range(1, pow(2, keta)):
        for y in range(R + 1, pow(2, keta)):
            if x > y:
                continue
            cnt -= ((y % x) == (x ^ y))
    print(cnt)

# solve_naive(L_, R_)

Submission status: Wrong Answer

Solution code:
mod=10**9+7
def solve(N):
    n=N.bit_length()
    dp=[[0 for i in range(4)] for j in range(n)]
    dp[0][0]=1+(N%2==1)
    dp[0][1]=1+2*(N%2==1)
    dp[0][2]=2
    dp[0][3]=3
    for i in range(1,n):
        for j in range(4):
            if j==0:
                if N>>i&1==1:
                    dp[i][j]=dp[i-1][2]+dp[i-1][1]
                else:
                    dp[i][j]=dp[i-1][0]
            elif j==1:
                if N>>i&1==1:
                    dp[i][j]=dp[i-1][3]+2*dp[i-1][1]
                else:
                    dp[i][j]=dp[i-1][1]
            elif j==2:
                dp[i][j]=dp[i-1][2]+dp[i-1][3]
            else:
                dp[i][j]=3*dp[i-1][3]

    return dp[-1][0]-1

def extra(N):
    if N==0:
        return 0
    n=N.bit_length()
    dp=[[0 for i in range(4)] for j in range(n)]
    dp[0][0]=1+(N%2==1)
    dp[0][1]=2+(N%2==1)
    dp[0][2]=2
    dp[0][3]=3
    for i in range(1,n):
        for j in range(4):
            if j==0:
                if N>>i&1==1:
                    dp[i][j]=dp[i-1][2]+dp[i-1][1]
                else:
                    dp[i][j]=dp[i-1][0]
            elif j==1:
                if N>>i&1==1:
                    dp[i][j]=2*dp[i-1][3]+dp[i-1][1]
                else:
                    dp[i][j]=2*dp[i-1][1]
            elif j==2:
                dp[i][j]=dp[i-1][2]+dp[i-1][3]
            else:
                dp[i][j]=3*dp[i-1][3]

    return dp[-1][0]-1

L,R=map(int,input().split())
print((solve(R)-extra(L-1))%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



l, r = LI()
L = r.bit_length()
dp = [[[[0] * 2 for _ in range(2)] for _ in range(2)] for _ in range(L+1)]
dp[0][0][0][0] = 1


for i in range(L):
    rd = r >> L - i - 1 & 1
    ld = l >> L - i - 1 & 1
    for l_flg in range(2):
        for r_flg in range(2):
            for c in range(2):
                for ri, li in ((1, 0), (1, 1), (0, 0)):
                    if c == 0 and ri == 1 and li == 0:
                        continue
                    if (l_flg == 0 and li < ld) or (r_flg == 0 and ri > rd):
                        continue
                    dp[i + 1][l_flg or li > ld][r_flg or ri < rd][c or (ri == 1 and li == 1)] += dp[i][l_flg][r_flg][c]
                    dp[i + 1][l_flg or li > ld][r_flg or ri < rd][c or (ri == 1 and li == 1)] %= mod

ret = 0
for a in range(2):
    for b in range(2):
        for d in range(2):
            ret += dp[L][a][b][d]

print(ret)

Submission status: Wrong Answer

Solution code:
l, r = input().split()
l = int(l)
r = int(r)

dp = [[[-1 for k in range(2)] for j in range(2)] for i in range(64)]

def bbin(num):
    res = []
    while num:
        res.append(num % 2)
        num //= 2

    return res

numr = bbin(r)
numl = bbin(l)
while len(numl) < len(numr):
    numl.append(0)

def rec(pos, brr, brl):
    global numl, numr, dp
    if pos < 0:
        return 1

    if dp[pos][brr][brl] != -1:
        return dp[pos][brr][brl]

    res = 0
    if brr:
        if brl:
            res = 3 * rec(pos - 1, brr, brl)
        else:
            if numl[pos] == 1:
                res = rec(pos - 1, brr, brl)
            else:
                res += (2 * rec(pos - 1, brr, 0))
                res += rec(pos - 1, brr, 1)
    else:
        if numr[pos] == 1:
            if brl:
                res += (2 * rec(pos - 1, 0, brl))
                res += rec(pos - 1, 1, brl)
            else:
                if numl[pos] == 1:
                    res += rec(pos - 1, 0, brl)
                else:
                    res += rec(pos - 1, 0, 0)
                    res += rec(pos - 1, 0, 1)
                    res += rec(pos - 1, 1, 0)
        else:
            if brl:
                res += rec(pos - 1, 0, brl)
            else:
                res += rec(pos - 1, 0, 0)

    dp[pos][brr][brl] = res % (10**9 + 7)
    return dp[pos][brr][brl]

c = 0
for i in range(len(numl) - 1, -1, -1):
    if numl[i] == 1:
        c += rec(i - 1, 1 if i < len(numl) - 1 else 0, 0)
        break
    else:
        c += rec(i - 1, 1 if i < len(numl) - 1 else 0, 1)

print(c % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

L_, R_ = map(int, raw_input().split())

ans = 0
for MSB in range(70):
    S = 2 ** MSB
    if S * 2 <= L_ or R_ < S:
        continue
    L, R = L_, R_
    if L <= S:
        L = S
    if 2 * S - 1 <= R:
        R = 2 * S - 1
    n1 = nL = nR = 0
    nLR = 1
    SL = SR = 1
    for i in range(MSB)[::-1]:
        flag1 = ((1 << i) & L != 0)
        flag2 = ((1 << i) & R != 0)
        SL *= 2
        SR *= 2
        SL += flag1
        SR += flag2
        n1 *= 3
        if flag1 and not flag2:
            nLR = 0
        if SR - SL >= 2:
            n1 += SR / 2 - SL / 2 - 1
            if not flag1:
                n1 += nL
            if flag2:
                n1 += nR
            if not flag1:
                nL *= 2
                nL += 1
            if flag2:
                nR *= 2
                nR += 1
            if not flag1 and flag2:
                nL += nLR
                nR += nLR
    if L == R:
        ans += 1
    else:
        ans += n1 + (SR - SL + 1) + nL + nR + 1
print ans % MOD

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

L_, R_ = map(int, raw_input().split())

ans = 0
for MSB in range(70):
    S = 2 ** MSB
    if S * 2 <= L_ or R_ < S:
        continue
    L, R = L_, R_
    if L <= S:
        L = S
    if 2 * S - 1 <= R:
        R = 2 * S - 1
    n1 = nL = nR = 0
    SL = SR = 1
    for i in range(MSB)[::-1]:
        flag1 = ((1 << i) & L != 0)
        flag2 = ((1 << i) & R != 0)
        SL *= 2
        SR *= 2
        SL += flag1
        SR += flag2
        n1 *= 3
        if SR - SL >= 2:
            n1 += SR / 2 - SL / 2 - 1
            if not flag1:
                n1 += nL
            if flag2:
                n1 += nR
            if not flag1:
                nL *= 2
                nL += 1
            if flag2:
                nR *= 2
                nR += 1
            if not flag1 and flag2:
                nL += 1
                nR += 1
    if L == R:
        ans += 1
    else:
        ans += n1 + (SR - SL + 1) + nL + nR + 1
print ans % MOD

Submission status: Wrong Answer

Solution code:
l,r= map(int, input().split())
div = 10**9 + 7
temp = 0
for i in range(l, r+1):
  for j in range(i, r+1):
    x,y = i,j
    if y % x == x ^ y:
      temp += 1
print(temp // div)

Submission status: Wrong Answer

Solution code:
from itertools import product
L, R = map(int, input().split())
MOD = 10**9 + 7

dp = [[[0, 0] for _ in range(2)] for _ in range(2)]
pp = [[[0, 0] for _ in range(2)] for _ in range(2)]
dp[0][0][0] = 1
for d in range(60, -1, -1):
    pp, dp = dp, pp
    dp = [[[0, 0] for _ in range(2)] for _ in range(2)]
    lb = L>>d & 1
    rb = R>>d & 1
    if d == 1:
        pass
    ans = 0
    for lrs in product((0,1), repeat=3):
        l, r, s = lrs
        for xy in product((0,1), repeat=2):
            nl, nr, ns = l, r, s
            x, y = xy
            if x and not y:
                continue
            if not s and x != y:
                continue
            if x and y:
                ns = 1
            if not l and not x and lb:
                continue
            if x and not lb:
                nl = 1
            if not r and y and not rb:
                continue
            if not y and rb:
                nr = 1
            dp[nl][nr][ns] += pp[l][r][s]
            dp[nl][nr][ns] %= MOD

print(sum(dp[l][r][s] for l in (0,1) for r in (0,1) for s in (0,1)))

Submission status: Wrong Answer

Solution code:
import numpy as np
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 3
    l_ = 0
    while True:
        if 2 ** (l_ + 1) - 1 > vr:
            break
        l_ += 1
    if 2 ** l_ - 1 == vr:
        return pow(3, l_, LARGE)
    else:
        return (pow(3, l_, LARGE) + 2 * get_r(vr - 2 ** l_)) % LARGE


def solve_F(L, R):
    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
        # print(res, left, right)
        le += 1
        left *= 2
        right *= 2
        right += 1
    return res


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


test = False
if __name__ == "__main__":
    if test:
        for L in range(1, 1001):
            for R in range(L, 1001):
                res = solve_F(L, R)
                res_g = solve_greed_f(L, R)
                if res != res_g:
                    print(L, R, res, res_g)
    else:
        L, R = map(int, input().split())
        print(solve_F(L, R))

Submission status: Wrong Answer

Solution code:
import numpy as np
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
    if 2 ** l_ - 1 == vr:
        return pow(3, l_, LARGE)
    else:
        return (pow(3, l_, LARGE) + 2 * get_r(vr - 2 ** l_)) % LARGE


def solve_F(L, R):
    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
    return res


test = False
if __name__ == "__main__":
    if test:
        for _ in range(100000):
            L, R = np.random.choice(10**10, 2)
            L, R = min(L, R) + 1, max(L, R) + 1
            print(L, R)
            res = solve_F(L, R)
    else:
        L, R = map(int, input().split())
        print(solve_F(L, R))

Submission status: Wrong Answer

Solution code:
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
    if 2 ** l_ - 1 == vr:
        return pow(3, l_, LARGE)
    else:
        return (pow(3, l_, LARGE) + 2 * get_r(vr - 2 ** l_)) % LARGE


def solve_F(L, R):
    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
    return res


import numpy as np
test = False
if __name__ == "__main__":
    if test:
        for _ in range(100000):
            L, R = np.random.choice(10**10, 2)
            L, R = min(L, R) + 1, max(L, R) + 1
            print(L, R)
            res = solve_F(L, R)
    else:
        L, R = map(int, input().split())
        print(solve_F(L, R))

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
L, R = map(int, input().split())
cnt = (R-L)
for x in range(L, R):
  for y in range(x+1, R+1):
    if (y % x) == (x ^ y):
      cnt += 1
print(int(cnt%(1e9+7)))

Submission status: Wrong Answer

Solution code:
def count(lb, rb):
    assert lb[0] == '1'
    assert rb[0] == '1'
    assert len(lb) == len(rb)
    dp = [1, 0, 0, 0]
    for lc, rc in zip(lb[1:], rb[1:]):
        ndp = [1, 0, 0, 0]
        if rc == '0':
            ndp[1] += dp[1]
            if lc == '1':
                ndp[0] -= 1
        else:
            ndp[1] += dp[1] * 2
            ndp[2] += dp[1]
            if lc == '0':
                ndp[1] += dp[0]
                ndp[3] += dp[0]
        if lc == '0':
            ndp[2] += dp[3]
            ndp[3] += dp[3] * 2
        else:
            ndp[3] += dp[3]
        ndp[2] += dp[2] * 3
        dp = ndp
    return sum(dp)


l, r = map(int, input().split())
lb = bin(l)[2:]
rb = bin(r)[2:]
ld = len(lb)
rd = len(rb)
ans = 0
MOD = 10 ** 9 + 7
for d in range(ld, rd + 1):
    tlb = lb if d == ld else '1' + '0' * (d - 1)
    trb = rb if d == rd else '1' * d
    ans = (ans + count(tlb, trb)) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def count(lb, rb, MOD):
    assert lb[0] == '1'
    assert rb[0] == '1'
    assert len(lb) == len(rb)
    i = 0
    for i, (lc, rc) in enumerate(zip(lb, rb)):
        if lc != rc:
            break
    else:
        return 1
    dp = [1, 0, 1]
    for lc, rc in zip(lb[i + 1:], rb[i + 1:]):
        ndp = [0, 0, 0]
        if rc == '0':
            ndp[0] += dp[0]
        else:
            ndp[0] += dp[0] * 2
            ndp[1] += dp[0]
            if lc == '0':
                ndp[0] += 1
                ndp[2] += 1
        if lc == '0':
            ndp[1] += dp[2]
            ndp[2] += dp[2] * 2
        else:
            ndp[2] += dp[2]
        ndp[1] += dp[1] * 3
        ndp[0] %= MOD
        ndp[1] %= MOD
        dp = ndp
    return sum(dp) + 1


l, r = map(int, input().split())
lb = bin(l)[2:]
rb = bin(r)[2:]
ld = len(lb)
rd = len(rb)
ans = 0
MOD = 10 ** 9 + 7
for d in range(ld, rd + 1):
    tlb = lb if d == ld else '1' + '0' * (d - 1)
    trb = rb if d == rd else '1' * d
    ans = (ans + count(tlb, trb, MOD)) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import *
MOD=10**9+7
@lru_cache(maxsize=None)
def solve(L,R):
  print(L, R)
  if L > R: return 0
  assert L >= 1
  if L == 1:
    return (1 + solve(2, R)) % MOD
  ans = solve(L//2,(R-1)//2) + solve((L+1)//2,R//2) + solve((L+1)//2,(R-1)//2)
  return ans % MOD
  
print(solve(*map(int,input().split())))

Submission status: Wrong Answer

Solution code:
l, r = map(int, input().split())
import math

ans = 0
inf = math.ceil(math.log(l, 2))
sup = math.floor(math.log(r+1, 2)) - 1
for i in range(inf, sup+1):
  ans += 3 ** i

for i in range(l, 2 ** inf):
  n = bin(i).count('0') - 1
  ans += 2 ** n

for i in range(2 ** (sup + 1), r + 1):
  n = bin(i).count('1') - 1
  ans += 2 ** n
print(ans % int(10**9+7))

Submission status: Wrong Answer

Solution code:
import math
p = 10**9+7

l,r = map(int, input().split())

if l==r:
  print(1)

def topbit(num):
  keta = math.floor(math.log2(num)) + 1
  ret = 2**keta-1 - num + 1
  return int(ret)

ret = [min(i, r-i+1, topbit(i))%p for i in range(l,r+1)]


print(sum(ret)%p)

Submission status: Wrong Answer

Solution code:
l,r=map(int,input().split())
yi=l^r
x=l
sum=0
while x <=r:
    y=x
    while y<=r:
        if yi==y//x:
            sum+=1
        y+=1
    x+=1
print(sum%(10**9+7))

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 最高次は等しくないといけないので、
# y % x = y-xになる
# yがxを包含していればok

mod = 1000000007

def ca(x, y):
    ct = 0
    for i in range(x, y+1):
        for j in range(i, y+1):
            if j % i == (j^i):
                ct += 1
    return ct

ans = 0
l, r = na()

dp = [0] * 4
dp[3] = 0
for i in range(60, -1, -1):
    ndp = [0] * 4
    base = 1<<i
    if base <= r and l < base*2:
        ptn = 0
        if base <= l:
            ptn += 1
        if r < base*2:
            ptn += 2
        ndp[ptn] += 1

    if (l>>i&1) == 0 and (r>>i&1) == 1:
        ndp[1] += dp[3]
        ndp[2] += dp[3]
    ndp[3] += dp[3]

    if (l >> i & 1) == 0:
        ndp[0] += dp[1]
        ndp[1] += dp[1]
    ndp[1] += dp[1]

    if (r >> i & 1) == 1:
        ndp[0] += dp[2]
        ndp[2] += dp[2]
    ndp[2] += dp[2]

    ndp[0] += dp[0] * 3

    for k in range(4):
        ndp[k] %= mod
    dp = ndp

print(sum(dp)% mod)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def solve(T):
    if T == 0:
        return 0
    ret = 0
    r = 0
    now = 0
    t = 1
    for i in range(1,60):
        if pow(2,i) - 1 <= T:
            ret += pow(3,i,Q)
            ret %= Q
            now = pow(2,i,Q)
            r = i
        else:
            break
    cnt = T - now
    while i > 0:
        i -= 1
        if cnt < pow(2,i):
            pass
        else:
            ret += pow(3,i,Q)*pow(2,t,Q)%Q
            t += 1
        ret %= Q
    return ret
            
    


def main():
    L, R = map( int, input().split())
    print((solve(R) - solve(L-1))%Q)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 最高次は等しくないといけないので、
# y % x = y-xになる
# yがxを包含していればok

mod = 1000000007

def ca(x, y):
    ct = 0
    for i in range(x, y+1):
        for j in range(i, y+1):
            if j % i == (j^i):
                ct += 1
    return ct

ans = 0
l, r = na()

dp = [0] * 4
dp[3] = 0
for i in range(60, -1, -1):
    ndp = [0] * 4
    base = 1<<i
    if base <= r and l < base*2:
        ptn = 0
        if base <= l:
            ptn += 1
        if r < base*2:
            ptn += 2
        ndp[ptn] += 1

    if (l>>i&1) == 0 and (r>>i&1) == 1:
        ndp[1] += dp[3]
        ndp[2] += dp[3]
    ndp[3] += dp[3]

    if (l >> i & 1) == 0:
        ndp[0] += dp[1]
        ndp[1] += dp[1]
    ndp[1] += dp[1]

    if (r >> i & 1) == 1:
        ndp[0] += dp[2]
        ndp[2] += dp[2]
    ndp[2] += dp[2]

    ndp[0] += dp[0] * 3

    for k in range(4):
        ndp[k] %= mod
    dp = ndp
    print(dp)

print(sum(dp)% mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
from heapq import heapify, heappop, heappush
from string import ascii_lowercase as abc
from bisect import bisect
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)
from fractions import gcd
def inpl(): return list(map(int, input().split()))

L = 1
R = 100
MOD = 10**9 + 7

DP = [[0]*61 for _ in range(61)]
DP[0][0] = 1
DP[0][1] = 1
DP[1][0] = 1
DP[1][1] = 1

for i in range(2, 61):
    for j in range(61):
        DP[i][j] = (DP[i][j] + DP[i-1][j] + DP[i-1][j-1]*(j>0))%MOD


def calc(x):
    res = 0
    add = 0
    for i in range(int.bit_length(x)-1, -1, -1):
        if x & 2**i:
            for j in range(61-add):
                res = (res + DP[i][j+add] * 2**j)%MOD
        else:
            add += 1
    return res

print((calc(R) - calc(L))%MOD)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def solve(T):
    if T == 0:
        return 0
    ret = 0
    r = 0
    now = 0
    t = 1
    for i in range(1,60):
        if pow(2,i) - 1 <= T:
            ret += pow(3,i,Q)
            ret %= Q
            now = pow(2,i,Q)
            r = i
        else:
            break
    cnt = T - now
    while i > 0:
        i -= 1
        if cnt < pow(2,i):
            pass
        else:
            ret += pow(3,i,Q)*t
            t += 1
        ret %= Q
    return ret
            
    


def main():
    L, R = map( int, input().split())
    print((solve(R) - solve(L-1))%Q)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
l,r=map(int,input().split())
m=10**9+7;f=[1]
for i in range(100):f+=[f[-1]*(i+1)%m]
def comb(aa,bb,mm):return f[aa]*pow(f[bb],mm-2,mm)*pow(f[aa-bb],mm-2,mm)%mm
s=bin(l)[2:]
n=len(s)
a=0
b=0
for i in range(1,n):
  if s[i]=="0":
    c=2**b%m
    for j in range(n-i):
      a+=comb(n-i,j,m)*c
      a%=m
      c*=2
    b+=1
s=bin(r)[2:]
n=len(s)
b=0
for i in range(1,n):
  if s[i]=="1":
    c=2**(n-b-1)%m
    for j in range(n-i):
      a+=comb(n-i,j,m)*c
      a%=m
      c//=2
    b+=1
for i in range(len(bin(l)[2:])+1,len(bin(r)[2:])+1):
  b=1
  for j in range(i):
    a+=comb(i,j,m)*b
    a%=m
    b*=2
print(a)

Submission status: Wrong Answer

Solution code:
l, r = map(int, input().split())
r += 1
ans = 0
def bit(x):
    ret = []
    for _ in range(64):
        ret.append(str(x % 2))
        x //= 2
    return ''.join(ret)

law = 10 ** 9 + 7
ans = 0
strl = bit(l)
strr = bit(r)
print(strr)
print(strl)
for i in range(64):
    if strl[i] > strr[i]:
        ans += 3 ** i % law
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
Q = 10**9+7
def solve(T):
    if T == 0:
        return 0
    ret = 0
    r = 0
    now = 0
    for i in range(1,60):
        if pow(2,i) - 1 <= T:
            ret += pow(3,i,Q)
            ret %= Q
            now = pow(2,i,Q)
            r = i
        else:
            break
    cnt = T - now
    while i > 0:
        i -= 1
        if cnt < pow(2,i):
            pass
        else:
            ret += pow(3,i,Q)
        ret %= Q
    return ret
            
    


def main():
    L, R = map( int, input().split())
    print((solve(R) - solve(L-1))%Q)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod=10**9+7
def solve(n):
    s=bin(n)[2:][::-1]
    m=len(s)
    X=[]
    for i in range(m)[::-1]:
        if s[i]=="1":
            X.append(i)
    res=0
    t=len(X)
    for i in range(t):
        res+=pow(3,X[i],mod)*pow(2,i,mod)
        res%=mod
    res+=pow(2,t,mod)-1
    res%=mod
    res*=(mod+1)//2
    res%=mod
    return res
L,R=map(int,input().split())
print(solve(R)-solve(L-1))

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

L, R = list(map(int, sys.stdin.readline().split()))


# ans = 0
# cnt = defaultdict(int)
# for x in range(1, R + 1):
#     for y in range(x, R + 1):
#         if y % x == y ^ x:
#             cnt[x + y % x] += 1
#             # print(y, x, y % x, bin(y), bin(x), bin(y % x), x + y % x)
#             ans += 1
# print(ans)
# print(cnt)

def count(R):
    if R == 1:
        return 1
    if R == 0:
        return 0
    # dp[d][n][桁より下を選んだ]
    dp = np.zeros((R.bit_length(), R.bit_length() + 1, 2), dtype=int)
    dp[-1][0][0] = 1
    for d in reversed(range(R.bit_length() - 1)):
        if R >> d & 1:
            for n in range(R.bit_length()):
                dp[d][n][1] += dp[d + 1][n][0]
                dp[d][n + 1][0] += dp[d + 1][n][0]
                dp[d][n][1] += dp[d + 1][n][1]
                dp[d][n + 1][1] += dp[d + 1][n][1]
        else:
            for n in range(R.bit_length()):
                dp[d][n][0] += dp[d + 1][n][0]
                dp[d][n][1] += dp[d + 1][n][1]
                dp[d][n + 1][1] += dp[d + 1][n][1]
        # print(dp[d], R >> d & 1)
        # if R >> d & 1:
        #     for n in range(R.bit_length()):
        #         dp[d][n + 1][1] += dp[d + 1][n][1]
        #         dp[d][n][1] += dp[d + 1][n][1]
        #         dp[d][n][1] += dp[d + 1][n][0]
        #         dp[d][n + 1][0] += dp[d + 1][n][0]
        # else:
        #     for n in range(R.bit_length()):
        #         dp[d][n][1] += dp[d + 1][n][1]
        #         dp[d][n + 1][1] += dp[d + 1][n][1]
        #         dp[d][n][0] += dp[d + 1][n][0]

    ans = (3 ** (R.bit_length() - 1) - 1) // 2 % MOD
    for i, r in enumerate(dp[0]):
        if r.sum():
            ans += pow(2, i, MOD) * r.sum()
            ans %= MOD
    return int(ans)


# print(count(R))
print((count(R) - count(L - 1)) % MOD)
# print(ans)

Submission status: Wrong Answer

Solution code:
l,r = map(int,input().split())
mod = 10**9+7



def f(x,y):
    if x == 1:
        return y
    
    if y <= pow(2,x-1):
        return f(x-1,y)
    else:
        return 2*f(x-1,y-pow(2,x-1))+pow(3,x-1)
        
if l == 1:
    ll = 0
elif l == 2:
    ll = 1
else:
    l -= 2
    p = 1
    c = 0
    s = 0
    while True:
        p *= 2
        s += p
        c += 1
        if l <= s:
            break
    ll = f(c,l-(s-p))+(pow(3,c)-1)//2
if r == 1:
    rr = 1
else:
    r -= 1
    p = 1
    c = 0
    s = 0
    while True:
        p *= 2
        s += p
        c += 1
        if r <= s:
            break

    rr = f(c,r-(s-p))+(pow(3,c)-1)//2


print((rr-ll)%mod)