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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache
mod=1000000007

@lru_cache()
def calc(l,r):
    if l>r:
        return 0
    if r==0:
        return 1
    b_l,b_r=l.bit_length(),r.bit_length()
    if b_l==b_r:
        return calc(l-(1<<(b_l-1)),r-(1<<(b_r-1)))
    if r==(1<<(b_r-1))-1 and l==0:
        return pow(3,b_r,mod)
    return (calc(l,r-(1<<(b_r-1)))+calc(l,(1<<(b_r-1))-1)+calc(0,r-(1<<b_r-1)))%mod

@lru_cache()
def solve(l,r):
    if l>r:
        return 0
    b_l,b_r=l.bit_length(),r.bit_length()
    if b_r>b_l:
        return (solve(l,(1<<b_r-1)-1)+calc(0,r-(1<<(b_r-1))))%mod
    a=1<<(b_l-1) if l else 0
    return calc(l-a,r-a)

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

Submission status: Accepted

Solution code:
L, R = map(int, input().split())
MOD = 10 ** 9 + 7
l = '{:060b}'.format(L)[::-1]
r = '{:060b}'.format(R)[::-1]
 
memo = [[[[-1 for l in range(2)] for k in range(2)] for j in range(2)] for i in range(60)]
 
def f(pos, flagX, flagY, flagZ):
    if pos == -1:
        return 1
    if memo[pos][flagX][flagY][flagZ] != -1:
        return memo[pos][flagX][flagY][flagZ]
    ret = 0
    # x 0, y 0
    if flagX or l[pos] == '0':
        ret += f(pos - 1, flagX, 1 if r[pos] == '1' else flagY, flagZ)
    # x 0, y 1
    if (flagX or l[pos] == '0') and (flagY or r[pos] == '1') and flagZ:
        ret += f(pos - 1, flagX, flagY, flagZ)
    # x 1, y 1
    if flagY or r[pos] == '1':
        ret += f(pos - 1, 1 if l[pos] == '0' else flagX, flagY, 1)
    ret %= MOD
    memo[pos][flagX][flagY][flagZ] = ret
    return ret
 
ans = f(59, 0, 0, 0)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
l,r = [int(i) for i in readline().split()]

def make_dp(init, size):
    res = "[{}]*{}".format(init,size[-1])
    for i in reversed(size[:-1]):
        res = "[{} for _ in [0]*{}]".format(res,i)
    return eval(res)


MOD = 10**9 + 7

R = bin(r)[2:]
L = bin(l)[2:]
L = "0"*(len(R)-len(L)) + L

dp = make_dp(0,(len(R)+1,2,2,2))
dp[0][0][0][0] = 1
for i, (r,l) in enumerate(zip(R,L)): #i桁目からi+1桁目に遷移
    ri = int(r)
    li = int(l)
    for is_less in range(2):
        for is_more in range(2):
            for is_nonzero in range(2):
                for dl in range(0 if is_more else li,2):
                    for dr in range(dl, 2 if is_less else ri+1): # d: i+1桁目の数字
                        dp[i+1][is_nonzero or dr != 0][is_more or li < dl][is_less or dr < ri] += dp[i][is_nonzero][is_more][is_less]*(dr==dl or is_nonzero)
                        dp[i+1][is_nonzero or dr != 0][is_more or li < dl][is_less or dr < ri] %= MOD

#print(dp[-1])
ans = 0
for i in range(2):
    for j in range(2):
        for k in range(2):
            ans += dp[-1][i][j][k]

print(ans%MOD)

Submission status: Accepted

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

def func(x, y):
	if y == 0:
		return 1
	dp = [[0 for _ in range(6)] for _ in range(61)]
	dp[60][0] = 1
	for i in range(59, -1, -1):
		if (y>>i) & 1 == 0 and (x>>i) & 1 == 0:
			dp[i][0] = dp[i+1][0]
			dp[i][1] = dp[i+1][1]
			dp[i][2] = dp[i+1][2]
			dp[i][3] = (dp[i+1][3]*2) % MOD
			dp[i][4] = dp[i+1][4]
			dp[i][5] = (dp[i+1][1] + dp[i+1][3] + dp[i+1][5]*3) % MOD
		elif (y>>i) & 1 == 1 and (x>>i) & 1 == 1:
			dp[i][0] = 0
			dp[i][1] = 0
			dp[i][2] = (dp[i+1][0] + dp[i+1][2]) % MOD
			dp[i][3] = (dp[i+1][1] + dp[i+1][3]) % MOD
			dp[i][4] = (dp[i+1][4]*2) % MOD
			dp[i][5] = (dp[i+1][4] + dp[i+1][5]*3) % MOD
		elif (y>>i) & 1 == 1 and (x>>i) & 1 == 0:
			dp[i][0] = 0
			dp[i][1] = (dp[i+1][0] + dp[i+1][1]) % MOD
			dp[i][2] = dp[i+1][2]
			dp[i][3] = (dp[i+1][2] + dp[i+1][3]*2) % MOD
			dp[i][4] = (dp[i+1][0] + dp[i+1][2] + dp[i+1][4]*2) % MOD
			dp[i][5] = (dp[i+1][1] + dp[i+1][3] + dp[i+1][4] + dp[i+1][5]*3) % MOD
		elif (y>>i) & 1 == 0 and (x>>i) & 1 == 1:
			dp[i][0] = 0
			dp[i][1] = 0
			dp[i][2] = 0
			dp[i][3] = (dp[i+1][1] + dp[i+1][3]) % MOD
			dp[i][4] = dp[i+1][4]
			dp[i][5] = (dp[i+1][5]*3) % MOD

	return (sum(dp[0]))%MOD

print(func(l, r))

Submission status: Accepted

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

*BL, = map(int, bin(L)[2:])
*BR, = map(int, bin(R)[2:])

a = len(BL)
b = len(BR)
BL = [0]*(len(BR) - len(BL)) + BL

BL.reverse()
BR.reverse()

memo = [[[-1]*2 for i in range(2)] for j in range(70)]
def dfs(i, p, q):
    if memo[i][p][q] != -1:
        return memo[i][p][q]
    if i == -1:
        memo[i][p][q] = 1
        return 1
    r = 0
    if p == q == 0:
        if BL[i] == 1 and BR[i] == 0:
            memo[i][0][0] = 0
            return 0
        if BL[i] == 1 or BR[i] == 0:
            r = dfs(i-1, 0, 0)
        else:
            r = (dfs(i-1, 0, 1) + dfs(i-1, 1, 0) + dfs(i-1, 0, 0)) % MOD
    elif p == 0:
        if BL[i] == 1:
            r = dfs(i-1, 0, 1)
        else:
            r = (2*dfs(i-1, 0, 1) + dfs(i-1, 1, 1)) % MOD
    elif q == 0:
        if BR[i] == 0:
            r = dfs(i-1, 1, 0)
        else:
            r = (2*dfs(i-1, 1, 0) + dfs(i-1, 1, 1)) % MOD
    else:
        r = 3 * dfs(i-1, 1, 1)
    memo[i][p][q] = r
    return r
ans = 0
for l in range(a-1, b):
    ans += dfs(l-1, +(not a-1 == l), +(not b-1 == l))
print(ans % MOD)

Submission status: Accepted

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
for i in range(60, -1, -1):
    ndp = [0] * 4
    base = 1<<i
    if base <= r and l < base*2:
        ptn = 0
        if base+1 <= l:
            ptn += 1
        if r < base*2-1:
            ptn += 2
        ndp[ptn] += 1

    if l>>i != r>>i:
        if (l>>i&1) == 0 and (r>>i&1) == 1:
            ndp[1] += dp[3]
            ndp[2] += dp[3]
    if ((l>>i)&(r>>i)) == (l>>i):
        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: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
P = 10**9+7
@lru_cache(maxsize=None)
def subcalc(l, r):
    if l < 0 or r < 0:
        print("ERROR")
        print("l, r =", l, r)
        print(1//0)
    if l > r: return 0
    if r == 0: return 1
    aa, bb = l.bit_length(), r.bit_length()
    if aa == bb:
        return subcalc(l-(1<<aa-1), r-(1<<bb-1))
    if (r & (r+1) == 0) and (l == 0):
        return pow(3, r.bit_length(), P)
    t = (subcalc(l, r-(1<<bb-1)) + subcalc(l, (1<<bb-1)-1) + subcalc(0, r-(1<<bb-1))) % P
    # print("subcalc", l, r, t)
    return t
 
@lru_cache(maxsize=None)
def calc(L, R):
    if L < 0 or R < 0:
        print("ERROR")
        print("l, r =", l, r)
        print(1//0)
    if L > R: return 0
    a = L.bit_length()
    b = R.bit_length()
    if b > a:
        t = (calc(L, (1<<b-1)-1) + calc(1<<b-1, R)) % P
        # print("calc", L, R, t)
        return t
    
        
        
    a = 1 << L.bit_length() - 1 if L else 0
    t = subcalc(L-a, R-a)
    # print("calc", L, R, t)
    return t
 
L, R = map(int, input().split())
print(calc(L, R))

Submission status: Accepted

Solution code:
from functools import lru_cache
P = 10**9+7
@lru_cache(maxsize=None)
def subcalc(l, r):
    if l > r: return 0
    if r == 0: return 1
    aa, bb = l.bit_length(), r.bit_length()
    if aa == bb:
        return subcalc(l-(1<<aa-1), r-(1<<bb-1))
    if (r & (r+1) == 0) and (l == 0):
        return pow(3, r.bit_length(), P)
    return (subcalc(l, r-(1<<bb-1)) + subcalc(l, (1<<bb-1)-1) + subcalc(0, r-(1<<bb-1))) % P

@lru_cache(maxsize=None)
def calc(L, R):
    if L > R: return 0
    a = L.bit_length()
    b = R.bit_length()
    if b > a:
        return (calc(L, (1<<b-1)-1) + calc(1<<b-1, R)) % P
    a = 1 << L.bit_length() - 1 if L else 0
    return subcalc(L-a, R-a)

L, R = map(int, input().split())
print(calc(L, R))

Submission status: Accepted

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

"""
R ????????1??????
y 0001????0??????
     ^d   ^rd
x 0001???????1??
             ^ld
L ???????????0???
"""

ans = 0

for d in range(70):
  if d<len(bin(L))-3:
    LD = []
  elif d==len(bin(L))-3:
    LD = [i for i in range(-1,d) if i==-1 or (L>>i&1)==0]
  else:
    LD = [d]
  if d<len(bin(R))-3:
    RD = [d]
  elif d==len(bin(R))-3:
    RD = [i for i in range(-1,d) if i==-1 or (R>>i&1)==1]
  else:
    RD = []
  for ld in LD:
    for rd in RD:
      a = 1
      for i in range(d):
        if i<ld:
          xc = [0, 1]
        elif i==ld:
          xc = [1]
        else:
          xc = [L>>i&1]
        if i<rd:
          yc = [0, 1]
        elif i==rd:
          yc = [0]
        else:
          yc = [R>>i&1]
        c = 0
        for x in xc:
          for y in yc:
            if y>=x:
              c += 1
        a *= c
      ans += a
print ans%(10**9+7)

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
P = 10**9+7
@lru_cache(maxsize=None)
def subcalc(l, r):
    if l < 0 or r < 0:
        print("ERROR")
        print("l, r =", l, r)
        print(1//0)
    if l > r: return 0
    if r == 0: return 1
    aa, bb = l.bit_length(), r.bit_length()
    if aa == bb:
        return subcalc(l-(1<<aa-1), r-(1<<bb-1))
    if (r & (r+1) == 0) and (l == 0):
        return pow(3, r.bit_length(), P)
    t = (subcalc(l, r-(1<<bb-1)) + subcalc(l, (1<<bb-1)-1) + subcalc(0, r-(1<<bb-1))) % P
    # print("subcalc", l, r, t)
    return t

@lru_cache(maxsize=None)
def calc(L, R):
    if L < 0 or R < 0:
        print("ERROR")
        print("l, r =", l, r)
        print(1//0)
    if L > R: return 0
    a = L.bit_length()
    b = R.bit_length()
    if b > a:
        t = (calc(L, (1<<b-1)-1) + calc(1<<b-1, R)) % P
        # print("calc", L, R, t)
        return t
    
        
        
    a = 1 << L.bit_length() - 1 if L else 0
    t = subcalc(L-a, R-a)
    # print("calc", L, R, t)
    return t

L, R = map(int, input().split())
print(calc(L, R))

Submission status: Accepted

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

"""
R ????????1??????
y 0001????0??????
     ^d   ^rd
x 0001???????1??
             ^ld
L ???????????0???
"""

ans = 0

for d in range(70):
  if d<len(bin(L))-3:
    LD = []
  elif d==len(bin(L))-3:
    LD = [i for i in range(-1,d) if i==-1 or (L>>i&1)==0]
  else:
    LD = [d]
  if d<len(bin(R))-3:
    RD = [d]
  elif d==len(bin(R))-3:
    RD = [i for i in range(-1,d) if i==-1 or (R>>i&1)==1]
  else:
    RD = []
  for ld in LD:
    for rd in RD:
      a = 1
      for i in range(d):
        # i<ld:  x==0 or 1
        # i==ld: x==1
        # i>ld:  x==L
        # i<rd:  y==0 or 1
        # i==rd: y==0
        # i>rd:  y==R
        # y>=x
        if i<ld and i<rd:
          a *= 3
        if i<ld and i==rd:
          a *= 1
        if i<ld and i>rd:
          a *= (R>>i&1)+1
        if i==ld and i<rd:
          a *= 1
        if i==ld and i==rd:
          a *= 0
        if i==ld and i>rd:
          a *= (R>>i&1)
        if i>ld and i<rd:
          a *= 2-(L>>i&1)
        if i>ld and i==rd:
          if (L>>i&1)==0:
            a *= 1
          else:
            a *= 0
        if i>ld and i>rd:
          if (L>>i&1)==(R>>i&1):
            a *= 1
          if (L>>i&1)==0 and (R>>i&1)==1:
            a *= 1
          if (L>>i&1)==1 and (R>>i&1)==0:
            a *= 0
      ans += a
print ans%(10**9+7)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from functools import lru_cache

MOD = 10 ** 9 + 7

"""
桁数が異なると矛盾
したがって商が1であることが必要
すると、xがyのsubsetであることが必要
一番上の桁を含むsubsetがx
"""

@lru_cache()
def F_naive(L,R):
    # 
    ret = 0
    ret += F((L+1)//2,(R+1)//2) # 2x,2y
    answer = 0
    for x in range(L,R+1):
        for y in range(x,R+1):
            if x.bit_length() == y.bit_length() and (x^y)+x == y:
                answer += 1
    return answer

@lru_cache()
def F(L,R):
    # x subset y かつ 2x > y
    if L < 0:
        L = 0
    if R < L:
        return 0
    if R == 0:
        return 0
    ret = 0
    # 下一桁が0,0ととる場合
    ret += F((L+1)//2, R//2)
    # 下一桁が0,1ととる場合
    # 2(2x) > (2y+1) iff 2x > y
    ret += F((L+1)//2,(R-1)//2)
    # 下一桁が1,0ととる場合
    # これはsubsetにならない

    # 下一桁が1,1ととる場合
    # 2(2x+1) > 2y+1 iff 2x >= y
    ret += G(L//2,(R-1)//2)
    return ret

@lru_cache()
def G(L,R):
    # x subset y かつ 2x >= y
    if L < 0:
        L = 0
    if R < L:
        return 0
    if R == 0:
        return 1
    ret = 0
    # 下一桁が0,0ととる場合
    ret += G((L+1)//2, R//2)
    # 下一桁が0,1ととる場合
    # 2(2x) >= (2y+1) iff 2x > y
    ret += F((L+1)//2,(R-1)//2)
    # 下一桁が1,0ととる場合
    # これはsubsetにならない

    # 下一桁が1,1ととる場合
    # 2(2x+1) >= 2y+1 iff 2x >= y
    ret += G(L//2,(R-1)//2)
    return ret

L,R = map(int,input().split())
answer = F(L,R) % MOD
print(answer)

Submission status: Runtime Error

Solution code:
L,R = map(int,input().split())
count = 0
for x in range(L,R+1):
  for y in range(L,R+1):
    print(x%y)
    surplus = y % x
    xor_xy = bin(x ^ y)
    xor_10 = int(xor_xy,2)
    if (suplus == xor_10):
      count += 1
result = count % (10 ** 9 + 7)
print(result)

Submission status: Runtime Error

Solution code:
L,R = map(int,input().split())
count = 0
for x in range(L,R+1):
  for y in range(L,R+1):
    #surplus = y % x
    #xor_xy = bin(x ^ y)
    #xor_10 = int(xor_xy,2)
    if ((y % x) == int(bin(x^y),2):
      count += 1
result = count % (10 ** 9 + 7)
print(result)

Submission status: Runtime Error

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 if numl[pos] == 0:
                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: Runtime Error

Solution code:

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()

Submission status: Runtime Error

Solution code:
    L,R=map(int,input().split())
    mod=10**9+7
     
    DP_ini=[[[0 for i in range(2)] for j in range(2)] for k in range(64)]
     
    import copy
    ANS=0
     
    for begin in range(64):
        DP=copy.deepcopy(DP_ini)
     
        if L<(1<<(begin+1)) and (1<<begin)<=R:
     
            if not(1<<begin <= L <  1<<(begin+1)) and not(1<<begin <= R <  1<<(begin+1)):
                DP[begin][0][0]=1
     
            elif 1<<begin <= L <  1<<(begin+1) and not(1<<begin <= R <  1<<(begin+1)):
                DP[begin][1][0]=1
     
            elif not(1<<begin <= L <  1<<(begin+1)) and 1<<begin <= R <  1<<(begin+1):
                DP[begin][0][1]=1
     
            else:
                DP[begin][1][1]=1
     
        for keta in range(begin-1,-1,-1):
     
            if L & (1<<keta)==0 and R & (1<<keta)==0:
                DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*0+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
                DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*1+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
                DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*2+DP[keta+1][1][1]*0
                DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1
     
            elif L & (1<<keta)!=0 and R & (1<<keta)==0:
                DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
                DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*1+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
                DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
                DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
     
            elif L & (1<<keta)==0 and R & (1<<keta)!=0:
                DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*1+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
                DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*2+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1
                DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*2+DP[keta+1][1][1]*1
                DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1
            else:
                DP[keta][0][0]=DP[keta][0][0]+DP[keta+1][0][0]*3+DP[keta+1][0][1]*1+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
                DP[keta][0][1]=DP[keta][0][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*2+DP[keta+1][1][0]*0+DP[keta+1][1][1]*0
                DP[keta][1][0]=DP[keta][1][0]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*1+DP[keta+1][1][1]*0
                DP[keta][1][1]=DP[keta][1][1]+DP[keta+1][0][0]*0+DP[keta+1][0][1]*0+DP[keta+1][1][0]*0+DP[keta+1][1][1]*1
     
        #print(begin,DP[0])
        ANS+=sum(DP[0][0])+sum(DP[0][1])
     
    print(ANS%mod)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
from collections import deque

n, q = map(int, input().split())
l=[0]*n
links = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  links[a-1].append(b-1)
  links[b-1].append(a-1)
for _ in range(q):
  p, x = map(int, input().split())
  l[p-1] += x
d = deque()
d.append((0, -1))
while len(d) != 0:
  i, p = d.popleft()
  for j in links[i]:
    if j==p:
      continue
    l[j] += l[i]
    d.append((j, i))
print(*l)

Submission status: Runtime Error

Solution code:
import collections, bisect

s = input()
t = input()

n = len(s)
d = collections.defaultdict(list)
for i, c in enumerate(s):
    d[c].append(i + 1)

m = len(t)
x = [0] * (m + 1) # 長さを記録
y = [0] * (m + 1) # 添え字を記録

for i in range(1, m + 1):
    c = t[i - 1]
    if not c in d:
        print(-1)
        exit()
    
    a = y[i - 1]
    ptr = bisect.bisect_right(d[c], y[i - 1])
    if ptr == len(d[c]):
        b = d[c][0]
    else:
        b = d[c][ptr]
    
    y[i] = b
    if a < b:
        x[i] = x[i - 1] + b - a
    else:
        x[i] = x[i - 1] + n - a + b
    
print(x[-1])

Submission status: Runtime Error

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

mod = 10**9+7
m = 64 +1
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

def f(N):
    S = bin(N)[2:]
    L = len(S)
    ret = pow(2,S.count("1")-1,mod)
    for i in range(L):
        if S[i] == "0" : continue
        c = S[:i].count("1")
        j = max(0,L-i-1)
        for k in range(j+1):
            if c+k == 0 : continue
            ret += pow(2,c+k-1,mod)*comb(j,k)
            ret %= mod
    return ret

ans = (f(R)-f(L-1))%mod
print(ans)

Submission status: Runtime Error

Solution code:
import itertools
l, r = map(int, input().split())
erange = list(range(l, r + 1))
cnt = 0
for (x, y) in itertools.combinations_with_replacement(erange, 2):
    if x > y:
        continue
    if y % x == y ^ x:
        cnt += 1

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

Submission status: Runtime Error

Solution code:
L,R = [int(i) for i in input().split(" ")]
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: Runtime Error

Solution code:
line = input().split()
L = int(line[0])
R = int(line[1])

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

Submission status: Runtime Error

Solution code:
import numpy as np

L,R = map(int,input().split())

ll = np.arange(L,R+1)
lllength = len(ll)
count=0

for i in range(lllength):
  x = ll[i]
  for j in range(lllength):
    if i+j > lllength-1:
      break
    y = ll[i+j]
    if y%x == y^x:
      count+=1
print(count%1000000007)

Submission status: Runtime Error

Solution code:
import numpy as np

L,R = map(int,input().split())

ll = np.arange(L,R+1)
lllength = len(ll)
count=0

for i in range(lllength):
  x = ll[i]
  for j in range(lllength):
    if i+j > lllength-1:
      break
    y = ll[i+j]
    if y%x == y^x:
      count+=1
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

L,R = map(int,input().split())

ll = np.arrange(L,R+1)

count=0

for i in range(ll):
  x = ll[i]
  for j in range(ll):
    if i+j > len:
      break
    y = ll[i+j]
    if y%x == y^x:
      count+=1