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 examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    def bitdp(l, r):
        n = r.bit_length()
        dp = defaultdict(int)
        dp[0, 0, 0, 0] = 1
        for i, less, greater, start in itertools.product(range(n), (0, 1), (0, 1), (0, 1)):
            R_ = 1 if less else (r>>(n-i-1))&1
            L_ = 0 if greater else (l>>(n-i-1))&1
            for y in range(R_ + 1):
                for x in range(L_, y + 1):
                    less_ = less or y < R_
                    greater_ = greater or L_ < x
                    start_ = start or (y==1 and x==1)

                    if not start and (y==1 and x==0):
                        # xorがあまりを確実に上回る
                        continue

                    dp[i + 1, less_, greater_, start_] += dp[i, less, greater, start]
                    dp[i + 1, less_, greater_, start_] %= mod
                    #print(dp[i + 1, less_, greater_, start_],i+1,less_,greater,start_,start)

        #for i in range(n):
        #    print(dp[i,0,0,0],dp[i,1,0,0],dp[i,0,1,0],dp[i,1,1,0])

        res = sum(dp[n, less, greater, 1] for less, greater in itertools.product((0, 1), (0, 1)))
        return res
    L, R = LI()
    ans = bitdp(L,R) % mod
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
l,r = map(int,input().split())
lb = l.bit_length()
rb = r.bit_length()
ans = 0
mod = 10**9+7
def ignorel(r):
  ret = 0
  cntr = 0
  rb = r.bit_length()
  for i in range(rb-1)[::-1]:
    if r&1<<i:
      ret += 2**cntr*3**i
      cntr += 1
  ret += 2**cntr
  return ret%mod
def ignorer(l):
  cntl = 0
  ret = 0
  lb = l.bit_length()
  for i in range(lb)[::-1]:
    if l&1<<i == 0:
      ret += 2**cntl*3**i
      cntl += 1
  ret += 2**cntl
  return ret%mod
for i in range(lb+1,rb):
  ans += 3**(i-1)
  ans %= mod
if lb != rb:
  ans += ignorer(l)
  ans += ignorel(r)
  ans %= mod
  print(ans)
else:
  def from0(x):
    if x == 0:
      return 1
    elif x == 1:
      return 3
    xb = x.bit_length()
    ret = 3**(xb-1)+2*from0(x-(1<<(xb-1)))
    return ret
  def calc(l,r):
    ret = 0
    lb = l.bit_length()
    rb = r.bit_length()
    if l > r:
      return 0
    if l == r:
      return 1
    if l == 2**(lb-1):
      return ignorel(r)
    elif r == 2**rb-1:
      return ignorer(l)
    for i in range(lb)[::-1]:
      if l&1<<i == 0 and r&1<<i:
        ret += from0((1<<i)-1-(l&(1<<i)-1))
        ret += from0(r&((1<<i)-1))
        ret += calc((l&((1<<i)-1))+(1<<i),(r&((1<<i)-1))+(1<<i))
        break
    return ret%mod
  ans += calc(l,r)
  print(ans%mod)

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 l[pos] == '0' or flagX:
      ret += f(pos - 1, flagX, 1 if flagY or r[pos] == '1' else 0, flagZ)
    # x 0 y 1
    if (l[pos] == '0' or flagX) and (r[pos] == '1' or flagY) and flagZ:
      ret += f(pos - 1, flagX, flagY, flagZ)
    # x 1 y 1
    if r[pos] == '1' or flagY:
      ret += f(pos - 1, 1 if l[pos] == '0' or flagX else 0, 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
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:
MOD = 10**9 + 7
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - m.i
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        res = 1
        while(m > 0):
            if m & 1:
                res = res * i % MOD 
            i = i * i % MOD
            m >>= 1
        return mint(res)
    def __truediv__(self, m):
        return mint(self.i * (m ** (MOD - 2)).i % MOD)
    def __repr__(self):
        return repr(self.i)

L, R = map(int, input().split())
dp = [[mint(0) for _ in range(4)] for _ in range(61)]

for d in range(60, 0, -1):
    l = L >> d - 1 & 1
    r = R >> d - 1 & 1
    
    if (L >> d - 1) == 0:
        if (R >> d - 1) > 1:
            dp[d-1][3] += 1
        elif (R >> d - 1) == 1:
            dp[d-1][2] += 1
    elif (L >> d - 1) == 1:
        if (R >> d - 1) > 1:
            dp[d-1][1] += 1
        else:
            dp[d-1][0] += 1

    # x bound, y bound
    if l == r:
        dp[d-1][0] += dp[d][0]
    elif l < r:
        dp[d-1][0] += dp[d][0]
        dp[d-1][1] += dp[d][0]
        dp[d-1][2] += dp[d][0]
    # x bound, y free
    if l == 0:
        dp[d-1][1] += dp[d][1] * 2
        dp[d-1][3] += dp[d][1]
    else:
        dp[d-1][1] += dp[d][1]
    # x free, y bound
    if r == 1:
        dp[d-1][2] += dp[d][2] * 2
        dp[d-1][3] += dp[d][2]
    else:
        dp[d-1][2] += dp[d][2]
    # x free, y free
    dp[d-1][3] += dp[d][3] * 3

print(sum(dp[0]))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    L, R = map(int, input().split())
    N = R.bit_length()
    mod = 1000000007

    dp = [[[0] * 2 for _ in range(4)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        l = L>>(N-i-1)&1
        r = R>>(N-i-1)&1

        # 0 0
        for j in range(2):
            dp[i+1][0][j] = (dp[i+1][0][j] + dp[i][0][j] * int(l == r == 0))%mod
            dp[i+1][1][j] = (dp[i+1][1][j] + dp[i][0][j] * int(r==1 and l==0) + dp[i][1][j] * int(l==0))%mod
            dp[i+1][2][j] = (dp[i+1][2][j] + dp[i][2][j] * int(r==0))%mod
            dp[i+1][3][j] = (dp[i+1][3][j] + dp[i][2][j] * int(r==1) + dp[i][3][j])
        # 0 1
        dp[i+1][0][1] = (dp[i+1][0][1] + dp[i][0][1] * int(l==0 and r==1))%mod
        dp[i+1][1][1] = (dp[i+1][1][1] + dp[i][1][1] * int(l==0))%mod
        dp[i+1][2][1] = (dp[i+1][2][1] + dp[i][2][1] * int(r==1))%mod
        dp[i+1][3][1] = (dp[i+1][3][1] + dp[i][3][1])%mod
        # 1 1
        dp[i+1][0][1] = (dp[i+1][0][1] + sum(dp[i][0]) * int(l==r==1))%mod
        dp[i+1][1][1] = (dp[i+1][1][1] + sum(dp[i][1]) * int(l==1))%mod
        dp[i+1][2][1] = (dp[i+1][2][1] + sum(dp[i][0]) * int(r==1 and l==0) + sum(dp[i][2] * int(r==1)))%mod
        dp[i+1][3][1] = (dp[i+1][3][1] + sum(dp[i][1]) * int(l==0) + sum(dp[i][3]))

    ans = 0
    for j in range(4):
        ans += dp[-1][j][1]
    print(ans%mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod = 10**9 + 7
K = 60

L, R = map(int, input().split())
Rb, Lb = [0], [0]
for i in range(K):
    Rb.append((R>>i)%2)
    Lb.append((L>>i)%2)
    if Rb[-1]:
        Rm = i+1
    if Lb[-1]:
        Lm = i+1
dp =[[1, 1, 1, 1] for _ in range(K+1)]
r = 0
for i in range(1, K+1):
    dp[i][0] = dp[i-1][0] * 3 % mod
    if Rb[i]:
        dp[i][1] = dp[i-1][1] * 2 + dp[i-1][0] % mod
    else:
        dp[i][1] = dp[i-1][1]

    if Lb[i]:
        dp[i][2] = dp[i-1][2]
    else:
        dp[i][2] = dp[i-1][2] * 2 + dp[i-1][0] % mod

    if Rb[i] and Lb[i]:
        dp[i][3] = dp[i-1][3]
    elif Rb[i]:
        dp[i][3] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3] % mod
    elif Lb[i]:
        dp[i][3] = 0
    else:
        dp[i][3] = dp[i-1][3]

    if Rm > i and Lm < i:
        r += dp[i-1][0]
    elif Rm > i and Lm == i:
        # このとき確実にLb[i] == 1
        r += dp[i-1][2]
    elif Rm == i and Lm < i:
        r += dp[i-1][1]
    elif Rm == i and Lm == i:
        r += dp[i-1][3]
    else:
        r += 0
    r = r % mod
print(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]

dp = [[[[-1 for _ in range(2)] for _ in range(2)] for _ in range(2)] for _ in range(60)]

def f(n,a,b,c):
    if n==-1:
        return 1
    if dp[n][a][b][c]!=-1:
        return dp[n][a][b][c]
    res = 0
    if a or l[n]=='0':
        res += f(n-1,a,1 if r[n]=='1' else b,c)
    if (a or l[n]=='0') and (b or r[n]=='1') and c:
        res += f(n-1,a,b,c)
    if b or r[n]=='1':
        res += f(n-1,1 if l[n]=='0' else a,b,1)
    res %= mod
    dp[n][a][b][c] = res
    return res

ans = f(59,0,0,0)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    L,R=map(int,input().split())
    L=map(int,bin(L)[2:].zfill(60))
    R=map(int,bin(R)[2:].zfill(60))

    dp=[[[0]*2 for _ in range(2)] for _ in range(2)]
    dp[0][0][0]=1 # dp[msb][mt][lt]

    for l,r in zip(L,R):
        ndp=[[[0]*2 for _ in range(2)] for _ in range(2)]
        for msb,mt,lt,x,y in product(range(2),repeat=5):
            if((not msb) and (x!=y)): continue
            if((not mt) and l>x): continue
            if((not lt) and y>r): continue
            if(x>y): continue
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]+=dp[msb][mt][lt]
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]%=MOD
        dp=ndp

    print(sum(dp[msb][mt][lt] for msb,mt,lt in product(range(2),repeat=3))%MOD)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    L,R=map(int,input().split())
    L=bin(L)[2:].zfill(60)
    R=bin(R)[2:].zfill(60)

    dp=[[[0]*2 for _ in range(2)] for _ in range(2)]
    dp[0][0][0]=1 # dp[msb][mt][lt]

    for l,r in zip(L,R):
        l=int(l); r=int(r)
        ndp=[[[0]*2 for _ in range(2)] for _ in range(2)]
        for msb,mt,lt,x,y in product(range(2),repeat=5):
            if((not msb) and (x!=y)): continue
            if((not mt) and l>x): continue
            if((not lt) and y>r): continue
            if(x>y): continue
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]+=dp[msb][mt][lt]
            ndp[max(msb,x*y==1)][max(mt,l<x)][max(lt,y<r)]%=MOD
        dp=ndp

    print(sum(dp[msb][mt][lt] for msb,mt,lt in product(range(2),repeat=3))%MOD)
resolve()

Submission status: Accepted

Solution code:
def p_f():
    from itertools import product
    L, R = map(int, input().split())
    mod = 10 ** 9 + 7
    # dp[i][j][k][l]: iは桁, jはL<=xか, kはy<=Rか, lは桁数が同じか
    dp = [[[[0] * 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)):
        # LとRのiビット目を取り出す
        lb = L >> i & 1
        rb = R >> i & 1
        for j, k, l in product(range(2), repeat=3):
            # 前の状態
            pre = dp[i + 1][j][k][l]
            for x, y in product(range(2), repeat=2):
                nj, nk, nl = j, k, l
                if x and (not y):  # xが1でyが0
                    continue
                if (not l) and x != y:
                    continue
                if x and y:
                    nl = 1
                # j: L <= x
                if (not j) and (not x) and lb:
                    continue
                if x and (not lb):
                    nj = 1
                # k: y <= R
                if (not k) and y and (not rb):
                    continue
                if (not y) and rb:
                    nk = 1
                dp[i][nj][nk][nl] += pre

    ans = 0
    for j, k, l in product(range(2), repeat=3):
        ans += dp[0][j][k][l]
        ans %= mod
    print(ans)


if __name__ == '__main__':
    p_f()

Submission status: Accepted

Solution code:
def p_f():
    L, R = map(int, input().split())
    mod = 10 ** 9 + 7
    # dp[i][j][k][l]: iは桁, jはL<=xか, kはy<=Rか, lは桁数が同じか
    dp = [[[[0] * 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)):
        # LとRのiビット目を取り出す
        lb = L >> i & 1
        rb = R >> i & 1
        for j in range(2):
            for k in range(2):
                for l in range(2):
                    # 前の状態
                    pre = dp[i + 1][j][k][l]
                    for x in range(2):
                        for y in range(2):
                            nj, nk, nl = j, k, l
                            if x and (not y):  # xが1でyが0
                                continue
                            if (not l) and x != y:
                                continue
                            if x and y:
                                nl = 1
                            # j: L <= x
                            if (not j) and (not x) and lb:
                                continue
                            if x and (not lb):
                                nj = 1
                            # k: y <= R
                            if (not k) and y and (not rb):
                                continue
                            if (not y) and rb:
                                nk = 1
                            dp[i][nj][nk][nl] += pre

    ans = 0
    for j in range(2):
        for k in range(2):
            for l in range(2):
                ans += dp[0][j][k][l]
                ans %= mod
    print(ans)

if __name__ == '__main__':
    p_f()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    L,R=map(int,input().split())
    L=bin(L)[2:].zfill(60)
    R=bin(R)[2:].zfill(60)
    dp=[[[0]*2 for _ in range(2)] for _ in range(2)]
    dp[0][0][0]=1 # dp[mt][lt][msb]

    for l,r in zip(L,R):
        l=int(l); r=int(r)
        ndp=[[[0]*2 for _ in range(2)] for _ in range(2)]
        for x,y,mt,lt,msb in product(range(2),repeat=5):
            if((not mt) and l>x): continue
            if((not lt) and y>r): continue
            if((not msb) and x!=y): continue
            if(x>y): continue
            ndp[max(mt,l<x)][max(lt,y<r)][max(msb,x*y)]+=dp[mt][lt][msb]
            ndp[max(mt,l<x)][max(lt,y<r)][max(msb,x*y)]%=MOD
        dp=ndp

    print(sum(dp[mt][lt][msb] for mt,lt,msb in product(range(2),repeat=3))%MOD)
resolve()

Submission status: Accepted

Solution code:
l,r=map(int,input().split())
M=len(bin(r))-2
L=format(l,"b").zfill(M)
R=format(r,"b")
mod=10**9+7
dp=[[0 for l in range(70)] for i in range(5)]
if L[0]=="1":
  dp[2][0]=1
else:
  dp[3][0]=1
  dp[0][0]=1
for i in range(1,M):
  if L[i]=="1" and R[i]=="1":
    dp[1][i]=(dp[0][i-1]+dp[1][i-1])%mod
    dp[2][i]=(dp[2][i-1])%mod
    dp[3][i]=(2*dp[3][i-1])%mod
    dp[4][i]=(dp[3][i-1]+3*dp[4][i-1])%mod
  elif L[i]=="1" and R[i]=="0":
    dp[1][i]=dp[1][i-1]+dp[0][i-1]
    dp[3][i]=dp[3][i-1]
    dp[4][i]=(dp[4][i-1]*3)%mod
  elif L[i]=="0" and R[i]=="1":
    dp[0][i]=dp[0][i-1]
    dp[1][i]=(2*dp[1][i-1]+dp[2][i-1])%mod
    dp[2][i]=dp[2][i-1]
    dp[3][i]=(dp[2][i-1]+dp[3][i-1]*2)%mod
    dp[4][i]=(dp[0][i-1]+dp[1][i-1]+dp[3][i-1]+dp[4][i-1]*3)%mod
  else:
    dp[0][i]=dp[0][i-1]
    dp[1][i]=(dp[1][i-1]*2)%mod
    dp[2][i]=dp[2][i-1]
    dp[3][i]=(dp[3][i-1])%mod
    dp[4][i]=(dp[0][i-1]+dp[1][i-1]+dp[4][i-1]*3)%mod
ans=0
for i in range(5):
  ans+=dp[i][M-1]
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
class ModInt(object):
    __MOD=10**9+7

    def __init__(self,x):
        self.__x=x%self.__MOD

    def __repr__(self):
        return str(self.__x)

    def __add__(self,other):
        return ModInt(self.__x+other.__x) if isinstance(other,ModInt) else ModInt(self.__x+other)

    def __sub__(self,other):
        return ModInt(self.__x-other.__x) if isinstance(other,ModInt) else ModInt(self.__x-other)

    def __mul__(self,other):
        return ModInt(self.__x*other.__x) if isinstance(other,ModInt) else ModInt(self.__x*other)

    def __truediv__(self,other):
        return ModInt(self.__x*pow(other.__x,self.__MOD-2,self.__MOD)) if isinstance(other, ModInt) else ModInt(self.__x*pow(other, self.__MOD-2,self.__MOD))

    def __pow__(self,other):
        return ModInt(pow(self.__x,other.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(self.__x,other,self.__MOD))

    __radd__=__add__

    def __rsub__(self,other):
        return ModInt(other.__x-self.__x) if isinstance(other,ModInt) else ModInt(other-self.__x)

    __rmul__=__mul__

    def __rtruediv__(self,other):
        return ModInt(other.__x*pow(self.__x,self.__MOD-2,self.__MOD)) if isinstance(other,ModInt) else ModInt(other*pow(self.__x,self.__MOD-2,self.__MOD))

    def __rpow__(self,other):
        return ModInt(pow(other.__x,self.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(other,self.__x,self.__MOD))
def resolve():
    from itertools import product
    L,R=map(int,input().split())
    D=R.bit_length()
    dp=[[[[ModInt(0)]*2 for _ in range(2)] for _ in range(2)] for _ in range(D+1)]
    dp[D][0][0][0]=ModInt(1)
    for d in range(D-1,-1,-1):
        lb=L>>d&1; rb=R>>d&1
        for i,j,m,x,y in product([0,1],repeat=5):
            ni,nj,nm=i,j,m
            if(x>y): continue
            # i:L<=X
            if(i==0 and lb>x): continue
            if(lb<x): ni=1
            # j:Y<=R
            if(j==0 and y>rb): continue
            if(y<rb): nj=1
            # m:MSB
            if(m==0 and x!=y): continue
            if(x==1 and y==1): nm=1
            dp[d][ni][nj][nm]+=dp[d+1][i][j][m];
    print(sum(dp[0][i][j][m] for i,j,m in product([0,1],repeat=3)))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
class ModInt(object):
    __MOD=10**9+7

    def __init__(self,x):
        self.__x=x%self.__MOD

    def __repr__(self):
        return str(self.__x)

    def __add__(self,other):
        return ModInt(self.__x+other.__x) if isinstance(other,ModInt) else ModInt(self.__x+other)

    def __sub__(self,other):
        return ModInt(self.__x-other.__x) if isinstance(other,ModInt) else ModInt(self.__x-other)

    def __mul__(self,other):
        return ModInt(self.__x*other.__x) if isinstance(other,ModInt) else ModInt(self.__x*other)

    def __truediv__(self,other):
        return ModInt(self.__x*pow(other.__x,self.__MOD-2,self.__MOD)) if isinstance(other, ModInt) else ModInt(self.__x*pow(other, self.__MOD-2,self.__MOD))

    def __pow__(self,other):
        return ModInt(pow(self.__x,other.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(self.__x,other,self.__MOD))

    __radd__=__add__

    def __rsub__(self,other):
        return ModInt(other.__x-self.__x) if isinstance(other,ModInt) else ModInt(other-self.__x)

    __rmul__=__mul__

    def __rtruediv__(self,other):
        return ModInt(other.__x*pow(self.__x,self.__MOD-2,self.__MOD)) if isinstance(other,ModInt) else ModInt(other*pow(self.__x,self.__MOD-2,self.__MOD))

    def __rpow__(self,other):
        return ModInt(pow(other.__x,self.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(other,self.__x,self.__MOD))
def resolve():
    from itertools import product
    L,R=map(int,input().split())
    D=61
    dp=[[[[ModInt(0)]*2 for _ in range(2)] for _ in range(2)] for _ in range(D+1)]
    dp[D][0][0][0]=ModInt(1)
    for d in range(D-1,-1,-1):
        lb=L>>d&1; rb=R>>d&1
        for i,j,m,x,y in product([0,1],repeat=5):
            ni,nj,nm=i,j,m
            if(x>y): continue
            # i:L<=X
            if(i==0 and lb>x): continue
            if(lb<x): ni=1
            # j:Y<=R
            if(j==0 and y>rb): continue
            if(y<rb): nj=1
            # m:MSB
            if(m==0 and x!=y): continue
            if(x==1 and y==1): nm=1
            dp[d][ni][nj][nm]+=dp[d+1][i][j][m];
    print(sum(dp[0][i][j][m] for i,j,m in product([0,1],repeat=3)))
resolve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

MOD = 10**9 + 7

def Fsmall(L,R):
    return sum(y-x == x^y for x in range(L,R+1) for y in range(x,min(x+x-1,R)+1))

@lru_cache(None)
def F(L,R):
    # x<=y<2x
    if R-L < 10:
        return Fsmall(L,R)
    f = 0
    # x=2a, y=2b
    f += F((L+1)//2,R//2)
    # x=2a+1,y=2b → これはルール違反
    # x=2a,y=2b+1
    f += F((L+1)//2,(R-1)//2)
    # x=2a+1,y=2b+1
    f += G(L//2,(R-1)//2)
    return f%MOD

def Gsmall(L,R):
    return sum(y-x == x^y for x in range(L,R+1) for y in range(x,min(x+x,R)+1))

@lru_cache(None)
def G(L,R):
    # x<=y<=2x
    if R-L < 10:
        return Gsmall(L,R)
    f = 0
    # x=2a, y=2b
    f += G((L+1)//2,R//2)
    # x=2a+1,y=2b → これはルール違反
    # x=2a,y=2b+1
    f += F((L+1)//2,(R-1)//2)
    # x=2a+1,y=2b+1
    f += G(L//2,(R-1)//2)
    return f%MOD

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

answer = F(L,R)
print(answer)

Submission status: Accepted

Solution code:
from itertools import product

MOD = 10**9 + 7

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

binR = bin(R+1)[2:]
maxD = len(binR)
binL = bin(L-1)[2:].zfill(maxD)

dp = [[[[0]*(2) for k in range(2)] for j in range(2)] for i in range(maxD+1)]
dp[0][0][0][0] = 1
for d, (Ld, Rd) in enumerate(zip(binL, binR)):
    Ld, Rd = int(Ld), int(Rd)
    for isLleX, isYleR, isNum in product(range(2), repeat=3):
        for x, y in [(0,0), (0,1), (1,1)]:
            if not isNum and (x, y) == (0, 1): continue
            if not isLleX and x < Ld: continue
            if not isYleR and y > Rd: continue
            isLleX2 = isLleX or x > Ld
            isYleR2 = isYleR or y < Rd
            isNum2 = isNum or y == 1
            dp[d+1][isLleX2][isYleR2][isNum2] += dp[d][isLleX][isYleR][isNum]
            dp[d+1][isLleX2][isYleR2][isNum2] %= MOD

print(dp[-1][1][1][1])

Submission status: Accepted

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

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, memo, left, right)
    # x 0, y 1
    if (flag_x or left[pos] == '0') and (flag_y or right[pos] == '1') and flag_z:
        ret += f(pos - 1, flag_x, flag_y, flag_z, memo, left, right)
    # x 1, y 1
    if flag_y or right[pos] == '1':
        ret += f(pos - 1, 1 if left[pos] == '0' else flag_x, flag_y, 1, memo, left, right)
    ret %= LARGE
    memo[pos][flag_x][flag_y][flag_z] = ret
    return ret


def solve_greed_f(L, R):

    res_g = 0

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

    return res_g


def main():

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

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

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

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

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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 + nLR
print ans % MOD