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:
def cmb(n, r):
    if n < r:
        return 0
    if r > n - r:
        return cmb(n, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n
    res = f[n]
    res *= invs[r]
    res %= mod
    res *= invs[n - r]
    res %= mod
    return res


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

MAX_VAL = 10 ** 18
mb_len = MAX_VAL.bit_length()
f = [-1] * (mb_len + 1)
f[0] = 1
t = 1
for i in range(1, mb_len + 1):
    t *= i
    t %= mod
    f[i] = t

inv = pow(t, mod - 2, mod)
invs = [-1] * (mb_len + 1)
invs[mb_len] = inv
for i in range(mb_len - 1, 0, -1):
    inv *= (i + 1)
    inv %= mod
    invs[i] = inv

# f(x,y,r) - f(x,y,l-1)
# fは[1,r]における整数組数

dp = [0] * (mb_len + 1)
rr = 1
for i in range(1, mb_len + 1):
    t = 0
    for j in range(i):
        dp[i] += cmb(i - 1, j) * pow(2, j)
        dp[i] %= mod
    rr *= 2

ans = 0
while r > 0:

    rb = r.bit_length()
    print(ans, r, rb)

    if (r + 1).bit_length() == rb:
        ans += dp[rb - 1]
    else:
        ans += dp[rb]
    ans %= mod
    r -= pow(2, rb)

print(ans)
print(*dp)

"""
解けなかった
"""

Submission status: Wrong Answer

Solution code:
p = 10**9+7

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

if l==r:
  print(1)
else:
	ret = [min(i, r-i+1)%p for i in range(l,r+1)]
	print(sum(ret)%p)

Submission status: Wrong Answer

Solution code:
# 時間足りなすぎてうく

l, r = map(int, input().split())
MOD = 10 ** 9 + 7

# A000120
# a(0) = 0, a(2*n) = a(n), a(2*n+1) = a(n) + 1
def h2(a):
    if a == 0:
        return 0
    return h2(a // 2) + (a % 2)

# a(n) = 3*a(floor(n/2)) + (n mod 2)*2^A000120(n-1). - M. F. Hasler, May 03 2009
def h(a):
    if a == 0:
        return 0
    return (3 * h(a // 2) + (a % 2) * pow(2, h2(a - 1), MOD)) % MOD

def is_pow(n):
    while n > 1:
        if n % 2 != 0:
            return False
        n //= 2
    return True

# aに依存
def g(a, b):
    if is_pow(a):
        return b - a + 1
    if is_pow(a + 1):
        return 0;
    bit = bin(a)
    return 0

def f(a, b):
    if a < b:
        return f(a, a) + g(a, b)
    if a > b:
        return f(b, b)
    # Gould's sequence (https://en.wikipedia.org/wiki/Gould%27s_sequence)
    # 1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32,...
    # 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5
    ret = h(a)
    return ret

res = f(r, r) - f(l - 1, r) - f(r, l - 1) + f(l - 1, l - 1)
print((res % MOD + MOD) % 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
    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):
            ret += pow(3,i,Q)
        else:
            ret += pow(3,i,Q)*2
        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:
# xor でパスカルの三角形を作るとできるアレなのに…

mod = 10**9 + 7
L, R = map(int, input().split())
def solve(N):  # N 未満
    bl = N.bit_length()
    n = bl - 1
    ans = 0
    for i in range(n):
        ans += pow(3, i, mod)
    ans %= mod
    NN = 1 << n
    N -= NN  # N は[0, )
    NN >>= 1

    p = n-1
    m = 1
    while N>0:
        if N >= NN:
            N -= NN
            ans += pow(3, p, mod) * m % mod
            m <<= 1
        NN >>= 1
        p -= 1
    return ans % mod
print((solve(R+1)-solve(L))%mod)

Submission status: Wrong Answer

Solution code:
L,R = map(int,input().split())
MOD = 10**9+7
l = [0]*60
l[0] = 3
l[1] = 3
for i in range(2,60):
    l[i] = l[i-1]*3
Lbit = len(bin(L))-3
Rbit = len(bin(R))-3
print(sum(l[Lbit+1:Rbit])%MOD)

Submission status: Wrong Answer

Solution code:
L,R = map(int,input().split())
MOD = 10**9+7
l = [0]*60
l[0] = 3
l[1] = 3
for i in range(2,60):
    l[i] = l[i-1]*3
Lbit = len(bin(L))-3
Rbit = len(bin(R))-3
print(sum(l[Lbit+1:Rbit]))

Submission status: Wrong Answer

Solution code:
L,R = [int(i) for i in input().split(" ")]
if R >= 10**5:
    exit()
X = Y = list(range(L,R+1))
i =0
for x in X:
    for y in Y[X.index(x):]:
        if y%x == y ^ x:
            i+=1
print(i%(10**9+7))

Submission status: Wrong Answer

Solution code:
L,R = [int(i) for i in input().split(" ")]
if R >= 10**10:
    exit()
X = Y = list(range(L,R+1))
i =0
for x in X:
    for y in Y[X.index(x):]:
        if y%x == y ^ x:
            i+=1
print(i%(10**9+7))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return

#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return

#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return

#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return

#E
def E():
    s = input()
    t = input()
    n = len(s)
    m = len(t)
    d = defaultdict(lambda : [])
    for i in range(n):
        d[s[i]].append(i)
    f = [-1]*m
    alp = list("abcdefghijklmnopqrstuvwxyz")
    for i in range(m):
        if not d[t[i]]:
            print(-1)
            return
        j = bisect.bisect_right(d[t[i]],f[i-1])
        if j == len(d[t[i]]):
            f[i] = d[t[i]][0]
        else:
            f[i] = d[t[i]][j]
    ans = 0
    for i in range(m-1):
        if f[i] >= f[i+1]:
            ans += 1
    print(ans*n+f[-1]+1)
    return

#F
def F():
    def f(r):
        b = list(bin(r)[2:])
        n = r.bit_length()
        for i in range(n):
            b[i] = int(b[i])
        dp = [[[0 for i in range(n+1)] for j in range(2)] for k in range(n+1)]
        dp[0][0][0] = 1
        for i in range(n):
            for j in range(2):
                for k in range(n):
                    x = 1 if j else b[i]
                    for d in range(x+1):
                        ni,nj,nk = i+1, j or d < b[i], k+d
                        dp[ni][nj][nk] += dp[i][j][k]
                        dp[ni][nj][nk] %= mod
        res = 0
        s = 0
        for i in range(1,n+1):
            p = pow(2,i-1,mod)
            for j in range(2):
                s += dp[n][j][i]
                res += p*dp[n][j][i]
                res %= mod
        return res

    l,r = LI()
    k = (1<<(l-1).bit_length())-1
    k ^= l-1
    ans = f(r)-f(l-1)-f(k)
    print(ans%mod)

    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
s = input().split()
L,R = (int(i) for i in s)
x=L-1
y=L-1
lt=[]
rl=[]
while x != R:
  x=x+1
  y=L-1
  while y != R:
    y=y+1
    lt.append((x,y))
for i in lt:
  if (i[1]%i[0]) is (i[1] ^ i[0]):
    rl.append(i)
print(int(len(rl)%(10**9+7)))

Submission status: Wrong Answer

Solution code:
L, R = (int(i) for i in input().split())
s = 1e9 + 7

l =[]
for i in range(L, R + 1):
    l.append(i)

counter = 0
for i in range(len(l)):
    y = l[i]
    for j in range(len(l)):
        x = l[j]
        if y % x == x ^ y:
            counter += 1
        else:
            counter += 0
print(counter % s)

Submission status: Time Limit Exceeded

Solution code:
#TLE
L, R = map(int, input().split())
res = 0
good = []
for i in range(L, R+1):
    for j in range(i, R+1):
        a, b = i, j
        A, B = 0, 0
        flag = True
        while b > 0:
            if b & 1 < a & 1:
                flag = False
            A, B = a & 1, b & 1
            b >>= 1
            a >>= 1
        if flag == True and A == 1 and B == 1:
            res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
L,R=input().split()
l=int(L)
r=int(R)
pa=0
for i in range(l,r+1):
  for j in range(l,i+1):
    if i%j==i^j:
      pa+=1
print(pa%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
L,R=input().split()
l=int(L)
r=int(R)
pa=0
for i in range(l,r+1):
  for j in range(l,i+1):
    if i%j==i^j:
      pa+=1
print(pa)

Submission status: Time Limit Exceeded

Solution code:
LR=list(map(int,input().split()))
L=LR[0]
R=LR[1]

def xor(y,x):
    oby=bin(y)
    obx=bin(x)
    ly=len(oby)
    lx=len(obx)
    if ly>=lx:
        a="0b"
        for i in range(ly-lx):
            if oby[i+2]=="1":
                a+="1"
        for i in range(lx-2):
            if obx[i+2]=="1" and oby[ly-lx+i+2]=="0":
                a+="1"
            elif obx[i+2]=="0" and oby[ly-lx+i+2]=="1":
                a+="1"
            else:
                a+="0"
    else:
        a="0b"
        for i in range(lx-ly):
            if obx[i+2]=="1":
                a+="1"
        for i in range(ly-2):
            if oby[i+2]=="1" and obx[lx-ly+i+2]=="0":
                a+="1"
            elif oby[i+2]=="0" and obx[lx-ly+i+2]=="1":
                a+="1"
            else:
                a+="0"
    return int(a,2)

count=0
for i in range(R-L+1):
    x=L+i
    for j in range(R-x+1):
        y=x+j
        if y%x==xor(y,x):
                count+=1

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

Submission status: Time Limit Exceeded

Solution code:
#L,Rをリストとして受け取る
LR=list(map(int,input().split()))
L=LR[0]
R=LR[1]

#y,xを与えるとXORを返す関数を作る
def xor(y,x):
    oby=bin(y)
    obx=bin(x)
    ly=len(oby)
    lx=len(obx)
    if ly>=lx:
        a="0b"
        for i in range(ly-lx):
            if oby[i+2]=="1":
                a+="1"
        for i in range(lx-2):
            if obx[i+2]=="1" and oby[ly-lx+i+2]=="0":
                a+="1"
            elif obx[i+2]=="0" and oby[ly-lx+i+2]=="1":
                a+="1"
            else:
                a+="0"
    else:
        a="0b"
        for i in range(lx-ly):
            if obx[i+2]=="1":
                a+="1"
        for i in range(ly-2):
            if oby[i+2]=="1" and obx[lx-ly+i+2]=="0":
                a+="1"
            elif oby[i+2]=="0" and obx[lx-ly+i+2]=="1":
                a+="1"
            else:
                a+="0"
    return int(a,2)


#yとxの組を生成するループ
count=0
for i in range(R-L+1):
    x=L+i
    for j in range(R-x+1):
        y=x+j
#ここから求める計算をしていく
        if y%x==xor(y,x):
                count+=1

w=10**9+7
z=count%w

print(z)

Submission status: Time Limit Exceeded

Solution code:
l,r = map(int, input().split())
cnt = 0
for x in range(l,r+1):
    for y in range(x,r+1):
        if y%x == y ^ x:
            cnt += 1

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

Submission status: Time Limit Exceeded

Solution code:
L,R = map(int,input().split())
x = L
count = 0
times = R-L
for i in range(times+1):
    y = x
    #print('chk',x,y)
    for j in range(R-x+1):
        if y%x == y^x:
            #print(x,y,'-> o')
            count += 1
            y += 1

        else:
            #print(x,y,'-> x')
            y += 1

    x += 1


            
d = pow(10,9)+7
print(count%d)

Submission status: Time Limit Exceeded

Solution code:
L, R = map(int, input().split())
count = 0

for x in range(L,R+1):
  for y in range(x,R+1):
    if y%x==y^x:
      count += 1

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
l, r = map(int, input().split())
count = 0

for x in range(l, r + 1):
    for y in range(l, r + 1):
        if (x % y) == (x ^ y):
            count += 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
l, r = map(int, input().split())
s = 0
for x in range(l, r + 1):
    if 2 * x <= r + 1:
        s += 2 ** (bin(x).count('0') - 1) % (10 ** 9 + 7)
    else:
        for y in range(x, min(r + 1, 2 * x)):
            if y ^ x == y % x:
                s += 1
print(s % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
l, r = map(int, input().split())
s = 0
for x in range(l, r + 1):
    for y in range(x, min(r + 1, 2 * x)):
        if y ^ x == y % x:
            s += 1
print(s % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
L, R = map(int, input().split())
counta = 0
for x in range(L,R+1):
    for y in range(x, R+1):
        x_bin, y_bin =  bin(x), bin(y)
        if len(x_bin) == len(y_bin):
            if list(x_bin)[2] == '1':
                if list(y_bin)[2] == '1':
                    if y-x == x^y:
                        counta += 1
print(counta % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
L,R = list(map(int,input().split(" ")))
count= 0
for y in range(L,R+1):
    for x in range(L,R+1):
        if(y%x == y^x):
            count+=1
x= count%(10**9 +1)
print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from math import pow

# スペース区切りの整数の入力
L, R = map(int, input().split())

count = 0
for x in range(L, R+1):
    for y in range(x, R+1):
        if y % x == x ^ y:
            count += 1

print(int(count % (pow(10, 9) + 7)))

Submission status: Time Limit Exceeded

Solution code:

L, R = map(int, input().split())
res = 0
res += R - L + 1
for eachx in range(L, R+1):
    l = len(bin(eachx)) - 2
    upper = 2 ** l
    if not (eachx ^ (eachx-1)):
        res += eachx
        continue
    for eachy in range(eachx+1, min(R+1,upper)):
        if (eachy % eachx ) == (eachx ^ eachy): res += 1

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

Submission status: Time Limit Exceeded

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

def calc(keta,l,r):

    if keta==-1:
        if l>=L and r<=R:
            return 1
        else:
            return 0
    
    ANS=0
    
    if l==r==0:
        if (1<<keta)<=R:
            ANS=ANS+calc(keta-1,1<<keta,1<<keta)
            ANS%=mod

        ANS=ANS+calc(keta-1,0,0)
        ANS%=mod

    else:
        if l>=L and (1<<(keta+1))+r<=R:
            ANS=ANS+pow(3,keta+1,mod)
            ANS%=mod

        else:
            if r+(1<<keta)<=R:
                ANS+=calc(keta-1,l+(1<<keta),r+(1<<keta))
                ANS%=mod

            if r+(1<<keta)<=R and l+(1<<keta)>L:
                ANS+=calc(keta-1,l,r+(1<<keta))
                ANS%=mod

            if l+(1<<keta)>L:
                ANS+=calc(keta-1,l,r)
                ANS%=mod

    return ANS

print(calc(64,0,0))

Submission status: Time Limit Exceeded

Solution code:
l,r=map(int,input().split())
ans=0
for x in range(l,r+1):
  for y in range(x,r+1):
    if y%x==y^x:
      ans+=1
      if ans>1000000007:
        ans=ans%1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
L,R=map(int, input().split())

#print(L,R)

count=0
for x in range(L,R+1):
  for y in range(x,R+1):
    if y%x==x^y:
      count=count+1
      count=count%(10**9+7)

print(count)

Submission status: Time Limit Exceeded

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

def calc(keta,l,r):

    if keta==-1:
        if l>=L and r<=R:
            return 1
        else:
            return 0
    
    ANS=0
    
    if l==r==0:
        if (1<<keta)<=R:
            ANS=ANS+calc(keta-1,1<<keta,1<<keta)
            ANS%=mod

        ANS=ANS+calc(keta-1,0,0)
        ANS%=mod

    else:
        if l>=L and (1<<(keta+1))+r<=R:
            ANS=ANS+pow(3,keta+1,mod)
            ANS%=mod

        else:
            if r+(1<<keta)<=R:
                ANS+=calc(keta-1,l+(1<<keta),r+(1<<keta))
                ANS%=mod

            if r+(1<<keta)<=R and l+(1<<keta)>L:
                ANS+=calc(keta-1,l,r+(1<<keta))
                ANS%=mod

            if l+(1<<keta)>L:
                ANS+=calc(keta-1,l,r)
                ANS%=mod

    return ANS

print(calc(72,0,0))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

l, r  = [int(x) for x in stdin.readline().rstrip().split()]

ans = 0
for i in range(r-l+1):
    for j in range(r-l-i+1):
      ll = l+i
      rr = l+i+j
      if (rr%ll==ll^rr):
#          print(ll,rr,rr%ll,ll^rr, (rr%ll==ll^rr))
          ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#問題F
l,r=map(int, input().split())
a=0
for x in range(l,r+1):
    for y in range (x,r+1):
        if x <= y and (x ^ y)==y%x:
            a+=1
            #print(x, y)
if r <= 1000:
    print(a)
else:
    print(a%(1000000000+7))

Submission status: Time Limit Exceeded

Solution code:
L, R = map(int, input().split())

count=0
for x in range(L,R+1):
  for y in range(x, R+1):
    if y%x==y^x:
      count+=1
print(count%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
l,r=map(int,input().split())
a=10**9+7
counter=0
for x in range(l,r+1):
  for y in range(x,r+1):
    if float(y%x)==float(y^x):
      counter+=1
print(counter%a)

Submission status: Time Limit Exceeded

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

print(cnt % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#問題F
l,r=map(int, input().split())
a=0
for x in range(l,r+1):
    for y in range (l,r+1):
        if x <= y and (x ^ y)==y%x:
            a+=1
            #print(x, y)
print(a%(1000000000+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
L, R = (int(i) for i in input().split())
s = 1e9 + 7
l = range(L, R + 1)
counter = 0
for i in range(len(l)):
    x = l[i]
    for j in range(len(l)):
        y = l[j]
        if y % x == x ^ y:
            counter += 1
print(int(counter % s ))

Submission status: Time Limit Exceeded

Solution code:
def main():
  L,R = map(int,input().split())

  combs = ((x,y) for x in range(L,R+1) for y in range(x,R+1) if y%x == x^y)
  val = 10**9 + 7
  targets = len(list(combs))
  print(targets%val)
  return


if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
L, R = map(int,input().split())
mod = 10**9 + 7
count = 0
for i in range(L,R+1):
  for j in range(i,R+1):
    if j % i == j ^ i:
      count += 1
print(count % mod)

Submission status: Time Limit Exceeded

Solution code:
L, R = (int(i) for i in input().split())
s = 1e9 + 7
l = range(L, R + 1)
counter = 0
for i in range(len(l)):
    y = l[i]
    for j in range(len(l)):
        x = l[j]
        if y % x == x ^ y:
            counter += 1
        else:
            counter += 0
print(int(counter % s))

Submission status: Time Limit Exceeded

Solution code:
L, R = (int(i) for i in input().split())
s = 1e9 + 7

l =[]
for i in range(L, R + 1):
    l.append(i)

counter = 0
for i in range(len(l)):
    y = l[i]
    for j in range(len(l)):
        x = l[j]
        if y % x == x ^ y:
            counter += 1
        else:
            counter += 0
print(int(counter % s))

Submission status: Time Limit Exceeded

Solution code:
l, r = [int(i) for i in input().split()]

result = 0
for x in range(l, r+1):
    for y in range(x, r+1):
        if y % x == y ^ x:
            result += 1
print(result % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
L,R=map(int,input().split())
cnt=0

for x in range(L,R+1):
  for y in range(x,R+1):
    if( (y%x)==(y^x) ):
      cnt+=1

s=(10**9)+7

print(cnt%s)

Submission status: Accepted

Solution code:
m=10**9+7
l,r=map(int,input().split())
dp=[[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)] for _ in range(61)]

dp[60][0][0][0]=1

for i in reversed(range(60)):
  lb=l>>i&1
  rb=r>>i&1
  for j in range(2):
    for k in range(2):
      for s in range(2):
        pre=dp[i+1][j][k][s]
        for x,y in [(0,0),(0,1),(1,1)]: # excpet for (1,0) (because of x<y)
          nj,nk,ns=j,k,s
          # s
          if (s==0 and x==0 and y==1): continue; # skip for not x==y==1
          if (s==0 and x&y): ns=1;
          # j
          if (j==0 and lb==1 and x==0): continue; # skip for x<l
          if (j==0 and lb==0 and x==1): nj=1;
          # k
          if (k==0 and rb==0 and y==1): continue; # skip for r<y
          if (k==0 and rb==1 and y==0): nk=1;           
            
          dp[i][nj][nk][ns]+=pre
          dp[i][nj][nk][ns]%=m    
                  
ans=0             
for j in range(2):
  for k in range(2):
    ans+=dp[0][j][k][1]
    ans%=m
print(ans)

Submission status: Accepted

Solution code:
L, R = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
for d in range(62):  # 最上位 bit
    # dp[n] := n 桁目まで見た時に条件を満たすものが何個あるか
    # dp_small[n] := n 桁目まで見た時に、l と x が n 桁目まで一致していて条件を満たすものが何個あるか
    l = max(1<<d, L)
    r = min((2<<d)-1, R)
    if l > r:
        continue
    dp_small = [0] * (d+2)
    dp_ok = [0] * (d+2)
    dp_large = [0] * (d+2)
    dp_small_large = [0] * (d+2)
    dp_small_large[0] = 1
    for n in range(1, d+2):
        i = d-n+1
        dp_ok[n] = dp_ok[n-1] * 3 \
                 + (dp_small[n-1] if l>>i&1==0 else 0) \
                 + (dp_large[n-1] if r>>i&1 else 0)
        dp_small[n] = dp_small[n-1] * (1 if l>>i&1 else 2) \
                    + (dp_small_large[n-1] if l>>i&1 < r>>i&1 else 0)
        dp_large[n] = dp_large[n-1] * (2 if r>>i&1 else 1) \
                    + (dp_small_large[n-1] if l>>i&1 < r>>i&1 else 0)
        dp_small_large[n] = dp_small_large[n-1] if l>>i&1 <= r>>i&1 else 0
    a = dp_ok[d+1] + dp_large[d+1] + dp_small[d+1] + dp_small_large[d+1]
    ans += a
    # print(f"d={d},a={a},l={l},r={r}")
    # print(f"dp_ok={dp_ok}")
    # print(f"dp_small={dp_small}")
    # print(f"dp_large={dp_large}")
    # print(f"dp_small_large={dp_small_large}")
    # print()
print(ans % mod)

Submission status: Accepted

Solution code:
L, R = map(int, input().split())
dp = [[[[0]*2 for _ in range(2)] for _ in range(2)] for _ in range(65)]
dp[0][0][0][0] = 1
MOD = 10**9+7

for i in range(64):
    Li = (L>>(63-i))&1
    Ri = (R>>(63-i))&1
    
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for x in (range(2) if j else range(Li, 2)):
                    for y in range(2 if k else Ri+1):
                        if x==1 and y==0:
                            continue
                        
                        if l==0 and x==0 and y==1:
                            continue
                        
                        dp[i+1][j|(x>Li)][k|(y<Ri)][l|(x==1 and y==1)] += dp[i][j][k][l]
                        dp[i+1][j|(x>Li)][k|(y<Ri)][l|(x==1 and y==1)] %= MOD

ans = 0

for i in range(2):
    for j in range(2):
        for k in range(2):
            ans += dp[-1][i][j][k]
            ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

memo = {}
def solve(L, R):
    if (L, R) in memo:
        return memo[(L, R)]

    if L > R:
        res = 0
    elif L == 1:
        res = 1 + solve(2, R)
    else:
        res = (
            solve(L // 2, (R - 1) // 2) +
            solve((L + 1) // 2, R // 2) +
            solve((L + 1) // 2, (R - 1) // 2)
        )

    res %= mod
    memo[(L, R)] = res
    return res

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

Submission status: Accepted

Solution code:
mod = 10**9+7

# xと最上位bitが同じでx以下のもののスコア足し上げ
def countup(x, y):
    L1 = x.bit_length()
    x -= 1<<(L1-1)
    y -= 1<<(L1-1)
    L = x.bit_length()
    dp = [[[0, 0], [0, 0]] for _ in range(L+1)]
    # 立ってるbitがlこのもの
    dp[0][0][0] = 1
    for i in range(L):
        a = x&(1<<(L-1-i))
        b = y&(1<<(L-1-i))
        if a:
            if b:
                dp[i+1][0][0] = dp[i][0][0]
                dp[i+1][0][1] = 2*dp[i][0][1] % mod
                dp[i+1][1][0] = dp[i][1][0]
                dp[i+1][1][1] = (3*dp[i][1][1] + dp[i][0][1]) % mod
            else:
                dp[i+1][0][0] = dp[i][0][0]
                dp[i+1][0][1] = (dp[i][0][0] + 2*dp[i][0][1]) % mod
                dp[i+1][1][0] = (dp[i][0][0] + 2*dp[i][1][0]) % mod
                dp[i+1][1][1] = (3*dp[i][1][1] + dp[i][0][1] + dp[i][1][0]) % mod 
        else:
            if not b:
                dp[i+1][0][0] = dp[i][0][0]
                dp[i+1][0][1] = dp[i][0][1]
                dp[i+1][1][0] = 2*dp[i][1][0] % mod
                dp[i+1][1][1] = (3*dp[i][1][1] + dp[i][1][0]) % mod
            else:
                dp[i+1][0][1] = dp[i][0][1]
                dp[i+1][1][0] = dp[i][1][0]
                dp[i+1][1][1] = 3*dp[i][1][1] % mod
    return sum(dp[L][0]) + sum(dp[L][1]) % mod


def main():
    Left, Right = map(int, input().split())
    ans = 0
    while True:
        # print(bin(Right))
        bl = Left.bit_length()
        br = Right.bit_length()
        if bl == br:
            ans = (ans + countup(Right, Left)) % mod
            break
        else:
            ans = (ans + countup(Right, (1<<(br-1)))) % mod
            Right = (1<<(br-1))-1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(L,R):
    n=R.bit_length()
    dp=[[0 for i in range(8)] for i in range(n)]
    if R&1==1 and L&1==1:
        dp[0][0]=1
        dp[0][1]=1
        dp[0][2]=2
        dp[0][3]=3
        dp[0][4]=1
        dp[0][5]=1
        dp[0][6]=2
        dp[0][7]=3
    elif R&1==1 and L&1==0:
        dp[0][0]=2
        dp[0][1]=3
        dp[0][2]=2
        dp[0][3]=3
        dp[0][4]=2
        dp[0][5]=3
        dp[0][6]=2
        dp[0][7]=3
    elif R&1==0 and L&1==1:
        dp[0][0]=0
        dp[0][1]=0
        dp[0][2]=1
        dp[0][3]=1
        dp[0][4]=1
        dp[0][5]=1
        dp[0][6]=2
        dp[0][7]=3
    else:
        dp[0][0]=1
        dp[0][1]=1
        dp[0][2]=1
        dp[0][3]=1
        dp[0][4]=2
        dp[0][5]=3
        dp[0][6]=2
        dp[0][7]=3
    for i in range(1,n):
        for j in range(8):
            if j==0:
                if R>>i &1==1 and L>>i &1==1:
                    dp[i][j]=dp[i-1][1]
                elif R>>i &1==1 and L>>i &1==0:
                    dp[i][j]=dp[i-1][4]+dp[i-1][3]
                elif R>>i&1 ==0 and L>>i&1 ==0:
                    dp[i][j]=dp[i-1][0]
            elif j==1:
                if R>>i &1==1 and L>>i &1==1:
                    dp[i][j]=dp[i-1][1]
                elif R>>i &1==1 and L>>i &1==0:
                    dp[i][j]=dp[i-1][5]+dp[i-1][3]+dp[i-1][1]
                elif R>>i&1==0 and L>>i&1==0:
                    dp[i][j]=dp[i-1][1]
            elif j==2:
                if R>>i&1==1:
                    dp[i][j]=dp[i-1][6]+dp[i-1][3]
                else:
                    dp[i][j]=dp[i-1][2]
            elif j==3:
                if R>>i&1==1:
                    dp[i][j]=dp[i-1][7]+2*dp[i-1][3]
                else:
                    dp[i][j]=dp[i-1][3]
            elif j==4:
                if L>>i&1==1:
                    dp[i][j]=dp[i-1][5]
                else:
                    dp[i][j]=dp[i-1][7]+dp[i-1][4]
            elif j==5:
                if L>>i&1==1:
                    dp[i][j]=dp[i-1][5]
                else:
                    dp[i][j]=2*dp[i-1][5]+dp[i-1][7]
            elif j==6:
                dp[i][j]=dp[i-1][6]+dp[i-1][7]
            else:
                dp[i][j]=3*dp[i-1][7]

    return dp[-1][0]

mod=10**9+7
L,R=map(int,input().split())
print(solve(L,R)%mod)