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:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[l,r]=i2()
z=10**9+7
dp=[[[[0 for l in range(2)]for k in range(2)]for j in range(2)]for i in range(61)]
dp[60][0][0][0]=1
for n in range(60)[::-1]:
 lb=l>>n&1
 rb=r>>n&1
 for x in range(2):
  for y in range(2):
   for i in range(2):
    for j in range(2):
     for k in range(2):
      ni=i+0
      nj=j+0
      nk=k+0
      if x>y:
         continue
      if k==0 and x!=y:
         continue
      if x&y:
         nk=1
      if i==0 and x<lb:
         continue
      if  x>lb:
         ni=1
      if j==0 and y>rb:
         continue
      if y<rb:
         nj=1
      dp[n][ni][nj][nk]+=dp[n+1][i][j][k]
      dp[n][ni][nj][nk]%=z
print((dp[0][1][1][1]+dp[0][0][1][1]+dp[0][1][0][1]+dp[0][0][0][1])%z)

Submission status: Accepted

Solution code:
mod = 10**9+7

def count(L, R):
    res = 0
    for j in range(70):
        res = (res + subcount(j, L, R)) % mod
    return res

def subcount(j, L, R):
    if j >= L.bit_length():
        return 0
    dp = [[0]*4 for _ in range(70)]
    
    cnt = 0
    if R.bit_length() != j+1:
        cnt += 1
    if L.bit_length() != j+1:
        cnt += 2
    dp[j][cnt] = 1
    
    for i in range(j, 0, -1):
        yf = R & (1<<(i-1))
        xf = L & (1<<(i-1))
        
        d0 = dp[i][0]
        if yf and xf:
            dp[i-1][0] += d0
            dp[i-1][2] += d0
            dp[i-1][3] += d0
        elif yf:
            dp[i-1][0] += d0
            dp[i-1][1] += d0
        elif xf:
            dp[i-1][2] += d0
        else:
            dp[i-1][0] += d0
        
        d1 = dp[i][1]
        if xf:
            dp[i-1][1] += d1
            dp[i-1][3] += 2*d1
        else:
            dp[i-1][1] += 2*d1
        
        d2 = dp[i][2]
        if yf:
            dp[i-1][2] += 2*d2
            dp[i-1][3] += d2
        else:
            dp[i-1][2] += d2
        
        d3 = dp[i][3]
        dp[i-1][3] += 3*d3
        
        dp[i-1][0] %= mod
        dp[i-1][1] %= mod        
        dp[i-1][2] %= mod
        dp[i-1][3] %= mod
        
    return sum(dp[0][i] for i in range(4))

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

Submission status: Accepted

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

mod = 10 ** 9 + 7

dp = [[[0] * 2 for _ in range(2)] for _ in range(2)]
dp[0][0][0] = 1

for i in range(60, -1, -1) :
    lb, rb = (L >> i) & 1, (R >> i) & 1
    dp_ = [[[0] * 2 for _ in range(2)] for _ in range(2)]
    for lf in range(2) :
        for rf in range(2) :
            for msb in range(2) :
                for l in range(2) :
                    for r in range(2) :
                        nlf, nrf, nmsb = lf, rf, msb
                        if l > r : continue
                        if not msb and l != r : continue
                        if l and r :
                            nmsb = 1
                        if not lf and l < lb : continue
                        if l > lb :
                            nlf = 1
                        if not rf and r > rb : continue
                        if r < rb :
                            nrf = 1
                        dp_[nlf][nrf][nmsb] += dp[lf][rf][msb]
                        dp_[nlf][nrf][nmsb] %= mod
    dp = dp_
    
ret = 0
for i in range(2) :
    for j in range(2) :
        for k in range(2) :
            ret += dp[i][j][k]
            
print(ret % mod)

Submission status: Accepted

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)) % MOD)

Submission status: Accepted

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

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    md = 10 ** 9 + 7
    l, r = map(int, input().split())
    n = int(math.log2(r)) + 1
    # dp[i][t][f][g] i桁目まで見て最上位が決定済みか(t)、L<xが確定(f)、y<Rが確定
    dp = [[[[0] * 2 for _ in range(2)] for __ in range(2)] for ___ in range(n + 1)]
    dp[0][0][0][0] = 1
    ans = 0
    for i in range(n):
        lk = l >> (n - 1 - i) & 1
        rk = r >> (n - 1 - i) & 1
        for t in range(2):
            for f in range(2):
                for g in range(2):
                    pre = dp[i][t][f][g]
                    for x, y in [(0, 0), (0, 1), (1, 1)]:
                        nt, nf, ng = t, f, g
                        if t == 0 and (x, y) == (0, 1): continue
                        if f == 0 and lk > x: continue
                        if g == 0 and y > rk: continue
                        if (x, y) == (1, 1): nt = 1
                        if lk == 0 and x == 1: nf = 1
                        if y == 0 and rk == 1: ng = 1
                        if i == n - 1:
                            ans = (ans + pre) % md
                        else:
                            dp[i + 1][nt][nf][ng] = (dp[i + 1][nt][nf][ng] + pre) % md
    print(ans)

main()

Submission status: Accepted

Solution code:
L, R = map(int, input().split())
MOD = 10 ** 9 + 7
l = '{:060b}'.format(L)[::-1] # 0左詰の二進数６０桁のstr　を逆向きにスライス
r = '{:060b}'.format(R)[::-1] # (桁数60 は　R<=10**18<2**60 より)

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

# flagZは、既にx＝y＝1の位があったかチェックしている(MSB)
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:
L,R = map(int,input().split())

mod = 10**9+7

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if j==0 : L2 = L
            elif L[j] == "1" : continue
            else : L2 = L[:j] + "1" + "?"*(N-j-1)

            tmp = 1
            for r,l in zip(R2,L2):
                if r=="0" and l=="1" : tmp *= 0 ; break
                elif r=="?" and l=="?" : tmp = tmp*3%mod
                elif r=="?" and l=="0" : tmp = tmp*2%mod
                elif r=="1" and l=="?" : tmp = tmp*2%mod
            ret += tmp
            ret %= mod
    return ret

print(f(L,R))

Submission status: Accepted

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

mod = 10**9+7

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            tmp = 1
            for r,l in zip(R2,L2):
                if r=="0" and l=="1" : tmp *= 0 ; break
                elif r=="?" and l=="?" : tmp = tmp*3%mod
                elif r=="?" and l=="0" : tmp = tmp*2%mod
                elif r=="1" and l=="?" : tmp = tmp*2%mod
            ret += tmp
            ret %= mod
    return ret

print(f(L,R))

Submission status: Accepted

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

mod = 10**9+7

def f(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            if L2[0] == "0" : break
            tmp = 1
            for r,l in zip(R2[1:],L2[1:]):
                if r=="0" and l=="1" : tmp *= 0 ; break
                if r=="?" and l=="?" : tmp = tmp*3%mod
                if r=="?" and l=="0" : tmp = tmp*2%mod
                if r=="1" and l=="?" : tmp = tmp*2%mod
            ret += tmp
            ret %= mod
    return ret

print(f(L,R))

Submission status: Accepted

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(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            if L2[0] == "0" : break
            tmp = 1
            for r,l in zip(R2[1:],L2[1:]):
                if r=="0" and l=="1" : tmp *= 0
                if r=="?" and l=="?" : tmp *= 3
                if r=="?" and l=="0" : tmp *= 2
                if r=="1" and l=="?" : tmp *= 2
                tmp %= mod
            ret += tmp
            ret %= mod
    return ret%mod

print(f(L,R))

Submission status: Accepted

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(L,R):
    if L>R : return 0
    R = bin(R)[2:]
    N = len(R)
    ret = f(L,int("0"+"1"*(N-1),2))
    L = bin(L)[2:]
    if len(L) != N : L = "1"+"0"*(N-1)
    for i in range(N):
        if R[i] == "0" : continue
        R2 = R[:i] + "0" + "?"*(N-i-1)
        if i==0: R2 = R
        for j in range(N):
            if L[j] == "1" and j!=0 : continue
            L2 = L[:j] + "1" + "?"*(N-j-1)
            if j==0 : L2 = L
            if L2[0] == "0" : break
            tmp = 1
            for r,l in zip(R2[1:],L2[1:]):
                if r=="0" and l=="1" : tmp *= 0
                if r=="?" and l=="?" : tmp *= 3
                if r=="?" and l=="0" : tmp *= 2
                if r=="1" and l=="?" : tmp *= 2
            ret += tmp
            ret %= mod
    return ret%mod

print(f(L,R))

Submission status: Accepted

Solution code:
import os
import os
import sys
from collections import defaultdict

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


def test(L, R):
    ans = 0
    cnt = defaultdict(int)
    for x in range(L, R + 1):
        for y in range(x, R + 1):
            if y % x == y ^ x:
                cnt[x + y % x] += 1
                ans += 1
    return ans


def solve(L, R):
    ret = L == 1
    for msb in range(R.bit_length()):
        r = min(R, (1 << msb + 1) - 1)
        l = max(L, (1 << msb))
        if l > r:
            continue
        # print(bin(r), bin(l))
        # dp[d][n][rより下を選んだ][lより上を選んだ]
        dp = np.zeros((r.bit_length(), 2, 2), dtype=int)
        for d in reversed(range(r.bit_length() - 1)):
            dp[-1][0][0] = 1
            if r >> d & 1:
                if l >> d & 1:
                    # r == 1, l == 1
                    # y1, x1
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][0] += dp[d + 1][0][0]
                    # y1, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][0][1] += dp[d + 1][0][1]
                    # y0, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][1] += dp[d + 1][0][1]
                else:
                    # r == 1, l == 0
                    # y1, x1
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][1] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][1] += dp[d + 1][0][0]
                    # y1, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][0] += dp[d + 1][0][0]
                    # y0, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][1][1] += dp[d + 1][0][1]
                    dp[d][1][0] += dp[d + 1][0][0]
            else:
                if l >> d & 1:
                    # r == 0, l == 1
                    # y1, x1
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    # y1, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    # y0, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][0][1] += dp[d + 1][0][1]
                else:
                    # r == 0, l == 0
                    # y1, x1
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][1] += dp[d + 1][1][0]
                    # y1, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    # y0, x0
                    dp[d][1][1] += dp[d + 1][1][1]
                    dp[d][1][0] += dp[d + 1][1][0]
                    dp[d][0][1] += dp[d + 1][0][1]
                    dp[d][0][0] += dp[d + 1][0][0]
            dp[d] %= MOD
        ret += dp[0].sum()
        ret %= MOD
    return int(ret)


print(solve(L, R))
# for l in range(1, R + 1):
#     for r in range(l, R + 1):
#         t1, t2 = solve(l, r), test(l, r)
#         if t1 != t2:
#             print(bin(l), bin(r), l, r, t1, t2)

Submission status: Accepted

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):
    if N==0:return 0
    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

def g(R,L):
    if L==0 : return 0
    Nr = len(bin(R))-2
    Nl = len(bin(L))-2
    if Nr!=Nl :
        R = int("1"*Nl,2)
        Nr = Nl
    ret = f(int("0"+"1"*(Nr-1),2))
    
    R = bin(R)[2:]
    L = bin(L)[2:]
    for i in range(Nr):
        if R[i] == "0": continue
        if i==0 : R2 = R
        else: R2 = R[:i] + "0" + "?"*(Nr-i-1)
        for j in range(Nl):
            if L[j] == "0" : continue
            if j==0 : L2 = L
            else: L2 = L[:j] + "0" + "?"*(Nl-j-1)
            tmp = 1
            for r,l in zip(R2,L2):
                if r==l=="?" : tmp *= 3
                if r=="?" and l=="0" : tmp *= 2
                if r=="1" and l=="?" : tmp *= 2
                if r=="0" and l=="1" : tmp *= 0
                tmp %= mod
            ret += tmp
    return ret

print((f(R)-g(R,L-1))%mod)

Submission status: Accepted

Solution code:
def f_coincidence(MOD=10 ** 9 + 7):
    # 参考: https://atcoder.jp/contests/abc138/submissions/7013926
    from itertools import product
    L, R = [int(i) for i in input().split()]

    dp = [[[[0 for s in range(2)] for k in range(2)]
           for j in range(2)] for i in range(61)]
    dp[60][0][0][0] = 1

    for i in range(59, -1, -1):
        lb = (L >> i) & 1  # 'b' はビット値であることを示す(以下も同じ)
        rb = (R >> i) & 1

        r2 = range(2)
        for j, k, s in product(r2, r2, r2):
            pre = dp[i + 1][j][k][s]
            # ビットごとに値を試す
            for xb, yb in product(r2, r2):
                # editorial の通り、このビットの組は元の条件を満たさない
                if xb == 1 and yb == 0:
                    continue
                # editorial の通り、これ以降は x <= y が満たされる

                nj, nk, ns = j, k, s
                # 今注目している桁でMSBが立つか？
                if s == 0 and xb != yb:
                    continue  # どちらかが立っていない
                if s == 0 and xb == 1 and yb == 1:
                    ns = 1  # ここで初めてMSBが立った

                # L <= x を満たすか？
                if j == 0 and xb == 0 and lb == 1:
                    # jが0のまま xb<lb となれば、L<=xになりようがない
                    # jが1なら、xbとlbがどうなっていようがL<=xである
                    continue
                if j == 0 and xb == 1 and lb == 0:
                    nj = 1  # この桁で L<=x が確定する

                # y <= R を満たすか？
                if k == 0 and yb == 1 and rb == 0:
                    continue  # L<=x の場合分けと同じこと
                if k == 0 and yb == 0 and rb == 1:
                    nk = 1

                # 反映
                dp[i][nj][nk][ns] += pre
                dp[i][nj][nk][ns] %= MOD

    ans = sum([dp[0][j][k][s] for j in range(2) for k in range(2)
               for s in range(2)]) % MOD
    return ans

print(f_coincidence())

Submission status: Accepted

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 = [dp[0], 0, 0, 0]
        if rc == '0':
            ndp[1] += dp[1]
            if lc == '1':
                ndp[0] = 0
        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: Accepted

Solution code:
MOD = 10**9 + 7

L, R = [int(item) for item in input().split()]
L_blen = L.bit_length()
R_blen = R.bit_length()

# dp[y loose/tight][x loose/tight][index]
dp = [[[0] * (R_blen+1) for _ in range(2)] for _ in range(2)]

for i in range(R_blen + 1):
    L_bit = L & (1 << R_blen - i)
    R_bit = R & (1 << R_blen - i)

    # Form R's MSB to L's LSB can be the initial bit  
    curbit_idx = R_blen - i + 1
    if curbit_idx <= R_blen and curbit_idx >= L_blen:
        dp[R_blen == curbit_idx][L_blen == curbit_idx][i] += 1

    # R=0, L=0
    if not R_bit and not L_bit:
        # y=1, x=1
        dp[0][0][i] += dp[0][0][i-1] 
        dp[0][0][i] += dp[0][1][i-1] 
        # y=0, x=0
        dp[1][1][i] += dp[1][1][i-1] 
        dp[1][0][i] += dp[1][0][i-1] 
        dp[0][0][i] += dp[0][0][i-1] 
        dp[0][1][i] += dp[0][1][i-1] 
        # y=1, x=0
        dp[0][1][i] += dp[0][1][i-1] 
        dp[0][0][i] += dp[0][0][i-1] 

    # R=1, L=0
    if R_bit and not L_bit:
        # y=1, x=1
        dp[0][0][i] += dp[0][0][i-1] 
        dp[1][0][i] += dp[1][0][i-1] 
        dp[0][0][i] += dp[0][1][i-1] 
        dp[1][0][i] += dp[1][1][i-1] 
        # y=0, x=0
        dp[0][0][i] += dp[0][0][i-1] 
        dp[0][0][i] += dp[1][0][i-1] 
        dp[0][1][i] += dp[0][1][i-1] 
        dp[0][1][i] += dp[1][1][i-1] 
        # y=1, x=0
        dp[0][0][i] += dp[0][0][i-1] 
        dp[1][0][i] += dp[1][0][i-1] 
        dp[0][1][i] += dp[0][1][i-1] 
        dp[1][1][i] += dp[1][1][i-1] 

    # R=0, L=1
    if not R_bit and L_bit:
        # y=1, x=1
        dp[0][0][i] += dp[0][0][i-1] 
        dp[0][1][i] += dp[0][1][i-1] 
        # y=0, x=0
        dp[0][0][i] += dp[0][0][i-1] 
        dp[1][0][i] += dp[1][0][i-1] 
        # y=1, x=0
        dp[0][0][i] += dp[0][0][i-1]

    # R=1, L=1
    if R_bit and L_bit:
        # y=1, x=1
        dp[0][0][i] += dp[0][0][i-1] 
        dp[1][0][i] += dp[1][0][i-1] 
        dp[0][1][i] += dp[0][1][i-1] 
        dp[1][1][i] += dp[1][1][i-1] 
        # y=0, x=0
        dp[0][0][i] += dp[1][0][i-1] 
        dp[0][0][i] += dp[0][0][i-1] 
        # y=1, x=0
        dp[1][0][i] += dp[1][0][i-1] 
        dp[0][0][i] += dp[0][0][i-1] 

    # Take MOD
    for i in range(2):
        for j in range(2):
            dp[i][j][i] %= MOD

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

Submission status: Accepted

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

Submission status: Accepted

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

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

#上から1桁ずつ4パターン(x0y0, x1y0, x0y1, x1y1)に場合分けして計算
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
    #x0, y0
    if flagX or l[pos] == '0':
        ret += f(pos-1, flagX, 1 if r[pos]=='1' else flagY, flagZ)
    #x0, y1
    if (flagX or l[pos] == '0') and (flagY or r[pos] == '1') and flagZ:
        ret += f(pos-1, flagX, flagY, flagZ)
    #x1, y1
    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:

import bisect
import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))
def getint2d(rows): return [getints() for _ in range(rows)]
def getgrid(rows): return [input() for _ in range(rows)]
def array1d(n, value): return [value for _ in range(n)]
def array2d(n, m, value): return [array1d(m, value) for _ in range(n)]

min_val,max_val=getints()

def get_key(pos, is_small, is_large, found):
    return ((pos * 2 + is_small) * 2 + is_large) * 2 + found

mod = 10**9 + 7
cache = [-1] * get_key(64,1,1,1)

def solve(pos, is_small, is_large, found):
    if pos < 0:
        return 1
    key = get_key(pos,is_small,is_large,found)
    res = cache[key]
    if res >= 0:
        return res

    res = 0
    for x in [0,1]:
        for y in [0,1]:
            if x == 1 and y == 0: continue
            if not is_small and x == 0 and (min_val >> pos & 1) == 1:
                continue
            if not is_large and y == 1 and (max_val >> pos & 1) == 0:
                continue
            if not found and x != y:
                continue
            new_is_small = True if x > (min_val >> pos & 1) else is_small
            new_is_large = True if y < (max_val >> pos & 1) else is_large
            new_found    = True if x == y and x == 1 else found
            res += solve(pos-1, new_is_small, new_is_large, new_found)

    res = res % mod
    cache[key] = res
    return res

print(solve(63, False, False, False))

Submission status: Accepted

Solution code:

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


dp = []

for i in range(62):

    nowA = []

    for i in range(2):

        nowB = []

        for i in range(2):

            nowC = []

            for i in range(2):

                nowC.append(0)

            nowB.append(nowC)

        nowA.append(nowB)

    dp.append(nowA)

dp[0][0][0][0] = 1
#print (dp[3][0][0][0])


for i in range(61):

    i += 1
    keta = 62-i

    lb = (L >> (keta-1)) % 2
    rb = (R >> (keta-1)) % 2


    for j in range(2):
        for k in range(2):
            for m in range(2):

                pre = dp[i-1][j][k][m]

                for x in range(2):
                    for y in range(2):

                        nj = j
                        nk = k
                        nm = m

                        if x == 1 and y == 0:
                            continue;

                        if x != y and m == 0:
                            continue;

                        if j == 0 and lb == 1 and x == 0:
                            continue;

                        if k == 0 and rb == 0 and y == 1:
                            continue;

                        if j == 0 and lb == 0 and x == 1:
                            nj = 1

                        if k == 0 and rb == 1 and y == 0:
                            nk = 1

                        if m == 0 and x == 1 and y == 1:
                            nm = 1


                        dp[i][nj][nk][nm] += dp[i-1][j][k][m]
                        dp[i][nj][nk][nm] %= 10 ** 9 +7

ans = 0

for j in range(2):
    for k in range(2):

        ans += dp[-1][j][k][1]

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

Submission status: Accepted

Solution code:
L, R = map(int, input().split())
mod = 10 ** 9 +7
l = '{:060b}'.format(L)
r = '{:060b}'.format(R)

memo = [[[[-1]*2 for i in range(2)] for j in range(2)] for k in range(60)]
def f(pos, flagL, flagR, flagM):
    if pos == 60:
        return 1
    if memo[pos][flagL][flagR][flagM] != -1:
        return memo[pos][flagL][flagR][flagM]
    ret = 0
    #(0, 0)
    if flagL or l[pos] == '0':
        ret+=f(pos+1, flagL, 1 if r[pos]=='1' else flagR, flagM)
    #(0, 1)
    if flagM and (flagL or l[pos]=='0') and (flagR or r[pos]=='1'):
        ret += f(pos+1, flagL, flagR, flagM)
    #(1, 1)
    if flagR or r[pos]=='1':
        ret += f(pos+1, 1 if l[pos]=='0' else flagL, flagR, 1)
    memo[pos][flagL][flagR][flagM] = ret%mod
    return ret%mod
print(f(0, 0, 0, 0)%mod)