Problem:


Score : 600 points

Problem Statement

You are given a positive integer N.
Find the number of the pairs of integers u and v (0≦u,v≦N) such that there exist two non-negative integers a and b satisfying a xor b=u and a+b=v.
Here, xor denotes the bitwise exclusive OR.
Since it can be extremely large, compute the answer modulo 10^9+7.

Constraints

1≦N≦10^{18}

Input

The input is given from Standard Input in the following format:

N

Output

Print the number of the possible pairs of integers u and v, modulo 10^9+7.

Sample Input 1

3

Sample Output 1

5

The five possible pairs of u and v are:

u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)

u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.）

u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.）

u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.）

u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.）

Sample Input 2

1422

Sample Output 2

52277

Sample Input 3

1000000000000000000

Sample Output 3

787014179



Sample input:
3


Sample output:
5

Submission status: Wrong Answer

Solution code:
def solve(n: int) -> int:
    mod = 1e9 + 7
    n_bin = '0' + bin(n)[2:]

    dp = [[0, 0, 0] for _ in range(len(n_bin))]
    dp[-1][0] = 1
    for i in range(len(n_bin) - 2, -1, -1):
        for s in range(3):
            for k in range(3):
                s2 = min(2, 2 * s + int(n_bin[len(n_bin) - i - 1]) - k)
                if s2 >= 0:
                    dp[i][s2] = (dp[i][s2] + dp[i + 1][s]) % mod

    return sum(dp[0]) % mod

n = int(input())
print(solve(n))

Submission status: Wrong Answer

Solution code:
def f(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    elif n % 2 == 0:
        return (2 * f(n // 2 - 1) + f(n // 2)) % 1000000007
    else:
        return (2 * f(n // 2) + f(n // 2 - 1)) % 10000000
n=int(input())
print(f(n))

Submission status: Wrong Answer

Solution code:
import sys

p=10**9+7
dthbit=lambda d,n: (n>>d)&1

def main(n):
    dp=[[0 for _ in range(3)] for _ in range(64)]
    dp[63][0]=1
    for d in range(62,-1,-1):
        b=dthbit(d,n)
        s=dp[d+1][:]
        dp[d][0]=dp[d+1][0]+(1^b)*dp[d+1][1] % p
        dp[d][1]=b*dp[d+1][0]+dp[d+1][1] % p
        dp[d][2]=(1+b)*dp[d+1][1]+3*dp[d+1][2] % p
    return sum(dp[0][:])

n=int(input())
print(main(n))

Submission status: Wrong Answer

Solution code:
import sys

p=10**9+7
dthbit=lambda d,n: (n>>d)&1

def main(n):
    dp=[[0 for _ in range(3)] for _ in range(64)]
    dp[63][0]=1
    for d in range(62,-1,-1):
        b=dthbit(d,n)
        s=dp[d+1][:]
        dp[d][0]=dp[d+1][0]+(1^b)*dp[d+1][1] % p
        dp[d][1]=b*dp[d+1][0]+dp[d+1][1] % p
        dp[d][2]=(1+b)*dp[d+1][1]+3*dp[d+1][2] % p
        print(s,dp[d+1][:],dp[d][:])
    return sum(dp[0][:])

n=int(input())
print(main(n))

Submission status: Wrong Answer

Solution code:
n = int(input())
print(n*(n-1)/2)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
M = len(bin(N)) - 2
L = bin(N)[2:]

dp = [[0] * 3 for _ in range(M + 1)]
dp[0][0] = 1

for i in range(M):
    if L[i] == '1':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][0] + dp[i][1]
        dp[i + 1][2] += 2 * dp[i][1] + 3 * dp[i][2]
    else:
        dp[i + 1][0] += dp[i][0] + dp[i][1]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][1] + 3 * dp[i][2]
    
    for j in range(3):
        dp[i + 1][j] %= MOD


print(sum(dp[M]))

Submission status: Wrong Answer

Solution code:
def ABC050D(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    k = n // 2
    if n % 2 == 0:
        return 2 * ABC050D(k - 1) + ABC050D(k)
    else:
        return 2 * ABC050D(k) + ABC050D(k - 1)

print(ABC050D(int(input())))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)

    def get(self, init=None):
        if self.v is None:
            return init
        else:
            return self.v


def main():
    N = format(int(input()), "b")
    D = len(str(N))
    dp = [[0 for _ in range(3)] for __ in range(D + 1)]

    dp[0][0] = 1
    for d in range(D):
        for k in range(3):
            for s in range(3):
                sd = 2 * s + int(N[d]) - k
                if sd > 2:
                    sd = 2
                if sd < 0:
                    continue
                dp[d + 1][sd] += dp[d][s]
                dp[d + 1][sd] %= mod

    print(sum(dp[D]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)

    def get(self, init=None):
        if self.v is None:
            return init
        else:
            return self.v


def main():
    N = format(int(input()), "b")
    D = len(str(N))
    dp = [[0 for _ in range(3)] for __ in range(D + 1)]

    dp[0][0] = 1
    print(N)
    for d in range(D):
        for k in range(3):
            for s in range(3):
                sd = 2 * s + int(N[d]) - k
                if sd > 2:
                    sd = 2
                if sd < 0:
                    continue
                dp[d + 1][sd] += dp[d][s]
                dp[d + 1][sd] %= mod

    print(sum(dp[D]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
mod = 10**9+7
ans = 0
for i in range(n+1):
    ans = (ans + (n - i + 1) // 2) % mod
    # print(ans, i, (n - i + 1)// 2)
print(ans + 1)

Submission status: Wrong Answer

Solution code:
n=int(input())
m=10**9+7
s=bin(n)[2:]
t=[[0,0,0]for i in range(len(s)+1)]
t[0][0]=1
for i in range(1,len(s)+1):
    if s[i-1]=="0":
        t[i][0]=t[i-1][0]+t[i-1][1]
        t[i][1]=t[i-1][1]
        t[i][2]=t[i-1][1]+t[i-1][2]*3
    else:
        t[i][0]=t[i-1][0]
        t[i][1]=t[i-1][0]+t[i-1][1]
        t[i][2]=t[i-1][2]*3+t[i-1][1]*2
    for j in range(3):
        t[i][j]%=m
print(sum(t[-1]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

MOD = 10 ** 9 + 7

n, *a = map(int, sys.stdin.read().split())

def main():
    c = Counter(a)
    if n & 1:
        if c.get(0, 0) != 1:
            return 0
        for i in range(2, n, 2):
            if c.get(i, 0) != 2:
                return 0
    else:
        for i in range(1, n, 2):
            if c.get(i, 0) != 2:
                return 0

    return pow(2, n // 2, MOD)
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
cnt = 0
for v in range(N+1):
    for u in range(v+1):
        if u == v:
            cnt += 1
            print(u,v)
            break
        for a in range(v+1):
            b = v-a
            if a^b == u:
                cnt += 1
                break
print(cnt%(10**9+7))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = LS()
    if a[1][0] == "+":
        print(int("".join(a[0])) + int("".join(a[2])))
    else:
        print(int("".join(a[0])) - int("".join(a[2])))
    return

#B
def B():
    _ = II()
    t = LI()
    tsum = sum(t)
    for _ in range(II()):
        p, x = LI()
        print(tsum - t[p - 1] + x)
    return

#C
def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    ans = 1
    if n & 1:
        for i in a:
            if i & 1:
                print(0)
                return
            d[i] += 1
        for a, b in d.items():
            if a:
                if b == 2:
                    ans *= 2
                    ans %= mod
                    continue
                print(0)
                return
            if b == 1:
                continue
            print(0)
            return
    else:
        for i in a:
            if i & 1:
                d[i] += 1
                continue
            print(0)
            return
        for a, b in d.items():
            if b == 2:
                ans *= 2
                ans %= mod
                continue
            print(0)
            return
    print(ans)
            
        
    return

#D
def D():
    n = II()
    binmax = len(bin(n)) - 2
    dp = [[0] * 3 for i in range(binmax + 1)]
    print(bin(n))
    dp[0][0] = 1
    for i in range(binmax):
        if (n >> binmax - i - 1) & 1:
            # nについて2進数のとき左からibit目が立つ

            # 前bit迄決めた時の和の差が0で今回bitが立つため
            # a,bのここのbitどちらかを立たせると和の差が0
            dp[i + 1][0] = dp[i][0] % mod

            # 前bitを決めた時の和の差が0で今回bitが立つため
            # a,bのここのbitを0にすると和の差が1 dp[i][0]
            # 前bitを決めた時の和の差が1で今回bitが立つため
            # この時点での和の差が3あるため
            # a,bのここのbitを1にすると和の差が1 dp[i][1]
            dp[i + 1][1] = (dp[i][0] + dp[i][1]) % mod

            # 前bitを決めた時の和の差が1で今回bitが立つため
            # この時点での和の差が3あるため
            # a,bのここのbitを(0,1),(0,0)にすると和の差が2以上
            # (0,1)と(1,0)は同じものなので dp[i][1]
            # 前bitを決めた時の和の差が2以上で今回bitが立つため
            # この時点での和の差が4以上あるため
            # 何をしても差は2以上で3通り dp[i][2]
            dp[i + 1][2] = (2 * dp[i][1] + 3 * dp[i][2]) % mod
        else:
            # nについて2進数のとき左からibit目が立たない

            # 前bit迄決めた時の和の差が0で今回bitが立たないため
            # a,bのここのbitを立たせないと和の差が0 dp[i][0]
            # 前bit迄決めた時の和の差が1で今回bitが立たないため
            # この時点での和の差が2あるため
            # a,bのここのbitを立たせると和の差が0 dp[i][1]
            dp[i + 1][0] = (dp[i][0] + dp[i][1]) % mod

            # 前bit迄決めた時の和の差が1で今回bitが立たないため
            # この時点での和の差が2あるため
            # a,bのここのbitをどちらかを立たせると和の差が1 dp[i][1]
            dp[i + 1][1] = dp[i][1] % mod

            # 前bitを決めた時の和の差が1で今回bitが立たないため
            # この時点での和の差が2あるため
            # a,bのここのbitを(0,0)にすると和の差が2以上 dp[i][1]
            # 前bitを決めた時の和の差が2以上で今回bitが立たないため
            # この時点での和の差が4以上あるため
            # 何をしても差は2以上で3通り dp[i][2]
            dp[i + 1][2] = (dp[i][1] + 3 * dp[i][2]) % mod

    print(sum(dp[-1]) % mod)

    return


#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
n = input()
print(int(n)*2 % 1000000007)

Submission status: Wrong Answer

Solution code:
n = input()
print(int(n)*2)

Submission status: Wrong Answer

Solution code:
# 桁DP 要復習

Submission status: Wrong Answer

Solution code:
from math import floor

mod = 1e9 + 7
n = int(input())
n += 2

com = n * (n - 1) / 2
print(int(floor(com / 2) % mod))

Submission status: Wrong Answer

Solution code:
import itertools
n=int(input())
c=[i for i in range(n+1)]
a=list(itertools.combinations_with_replacement(c, 2))
b=[1 for x in a if x[0]^x[1]==x[0]+x[1]]
print(len(b)%(10**9+7))

Submission status: Wrong Answer

Solution code:
N=int(input())
dp=[[0]*3 for i in range(62)]
dp[0][0]=1
for i in range(61):
  if N&(1<<(60-i)):
    dp[i+1][0]=dp[i][0]
    dp[i+1][1]=dp[i][0]+dp[i][1]
    dp[i+1][2]=2*dp[i][1]+3*dp[i][2]
  else:
    dp[i+1][0]=dp[i][0]+dp[i][1]
    dp[i+1][1]=dp[i][1]
    dp[i+1][2]=dp[i][1]+3*dp[i][2]
  for j in range(3):
    dp[i+1][j]%=10**9+7
print(sum(dp[61]))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


MOD = 10**9+7

n = 1000000000000000000
n_bit = len(bin(n)[2:])

dp = [[0]*4 for _ in range(n_bit+1)]
dp[0][0] = 1

for bit in range(n_bit):
    digit = int(bin(n)[2+bit:2+bit+1])
    
    if digit:
        dp[bit+1][0] = (dp[bit][0]) % MOD
        dp[bit+1][1] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1]) % MOD
        dp[bit+1][3] = (dp[bit][1] + 3*dp[bit][2] + 3*dp[bit][3]) % MOD
        
    else:
        dp[bit+1][0] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][1] = (dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1] + dp[bit][2]) % MOD
        dp[bit+1][3] = (2*dp[bit][2] + 3*dp[bit][3]) % MOD
        
print(sum(dp[n_bit]) % MOD)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
odd={0:1}
even={0:1,1:3}

def memo(N):
    if N ==0:
        return 1
    if N==1:
        return 2
    return memoodd((N-1)//2)+memoeven(N//2)


def memoodd(N):
    if N in odd:
        return odd[N]
#    a=memoodd((N-1)//2)
#    b=memoeven(N//2)
    odd[N] = memo(N)
    return odd[N]

def memoeven(N):
    if N in even:
        return even[N]
#    a=memoodd((N-1)//2)
#    b=memoeven(N//2)
#    c=memoodd((N-2)//2)
#    d=memoeven((N-1)//2)
#    return a+b+c+d
    even[N] = memo(N)+memo(N-1)
    return even[N]


print(memo(32))

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
x = []

for a,b in itertools.product(range(n),range(n)):
	tuple_temp = ()
	tuple_temp = (a ^ b,a + b)
	if tuple_temp[0] <= n and tuple_temp[1] <= n:
		x.append(tuple_temp)
	
set_tuple = set(tuple(x))
print(len(set_tuple) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def f(n):
    dic = {}
    for a in range(n+1):
        for b in range(a,n+1):
            if a^b<=n and a+b<=n:
                u = a^b
                v = a+b
                dic.setdefault(str(u)+','+str(v),0)
                #print(a,b,a^b,a+b)
    return len(dic)

n = int(input())

print(f(n))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    n1 = n + 1

    cnt = 0
    for u in range(n1):
        for v in range(u, n1):
            a = 0
            while True:
                b = v - a
                if a > b:
                    break
                if a ^ b == u:
                    cnt += 1
                    break
                a += 1

    print(cnt)




main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
mod = 10**9+7
cnt=[]
for u in range(N+1):
    for v in range(N+1):
        for a in range(v+1):
            if a^(v-a)==u:
                cnt.append((a,v-a))
                break
print(len(set(cnt))%mod)

Submission status: Time Limit Exceeded

Solution code:
N= int(input())

if N %2 ==0:
    dp=[[0 for i in range(2)] for j in range(((N//2)+1)**2)]

else:
    dp=[[0 for i in range(2)] for j in range(((N+1)//2)*((N+3)//2))]

res = 0
for i in range(0,N//2+1):
    for j in range(i,N-i+1):
        dp[res][0]=i^j
        dp[res][1]=i+j
        res = res+1

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

newdp = get_unique_list(dp)
print(len(newdp) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
fir=[]
t=0
for i in range(0,n+1):
    fir.append(i)
sec=fir
dodd=[]
for i in fir:
    for j in sec:
        u=i^j
        v=i+j
        if(u>=0 and u<=n and u<=v and v>=0 and v<=n):
            t+=1
            dodd.append((u,v))
print(len(set(dodd)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
cnt = 0
for u in range(N+1):
    for v in range(N+1):
        for a in range(v+1):
            b = v-a
            if a^b == u:
                cnt += 1
                break
print(cnt%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
digit = len(bin(n)) - 2
num_mod = 7 + 10 ** 9
l_ans = [[0 for j in range(n + 1 + 2 ** digit)] for i in range(digit + 1)]
l_ans[0][0] = 1

for d in range(digit):
  p = 2 ** (digit - d - 1)
  for c in range(n + 1):
    l_ans[d + 1][c] = (l_ans[d + 1][c] + l_ans[d][c]) % num_mod
    l_ans[d + 1][c + p] = (l_ans[d + 1][c + p] + l_ans[d][c]) % num_mod
    l_ans[d + 1][c + 2 * p] = l_ans[d][c] % num_mod
print(sum(l_ans[digit][:n + 1]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = len(bin(n)) - 2
mod = 10**9 + 7
dp = [[0 for j in range(n+1+2**d)] for i in range(d+1)]
dp[0][0] = 1
for i in range(d):
    t = 2 ** (d-i-1)
    for j in range(n+1):
        dp[i+1][j] = (dp[i+1][j] +  dp[i][j]) % mod
        dp[i+1][j+t] = (dp[i+1][j+t] + dp[i][j]) % mod
        dp[i+1][j+2*t] = dp[i][j] % mod
print(sum(dp[d][:n+1]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 入力
N = int(input())

a = 0
b = 0
u = 0
v = 0
X = 0
F = []
for v in range(0, N+1):
    b = 0
    while(2 * b <= v):
        a = v - b
        u = a ^ b
        #print(a,b,u,v)
        if u not in F:
            F.append(u)
        b = b + 1
    #print(F)
    X = X + len(F)
    F.clear()

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
n = int(input())
ans = set()

def dfs(a:int, b:int, digit:int, memo:set):
    u = a^b
    v = a+b
    
    if u > n or v > n:
        return 0
    
    else:        
        if digit == 0:
            memo.add((u,v))
            return 0
            
        else:
            dfs(a+pow(2,digit-1), b+pow(2,digit-1), digit-1, memo)
            dfs(a+pow(2,digit-1), b, digit-1, memo)
            dfs(a, b, digit-1, memo)
            
dfs(0,0,60,ans)

print(len(ans) % MOD)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
ans=0
for j in range(1,N+1):
    s=[]
    for i in range(int((j/2))+1):
        s.append(i^(j-i))
    ans+=len(set(s))
print((ans+1)%(10**9))

Submission status: Time Limit Exceeded

Solution code:
from functools import*
@lru_cache(0)
def d(n):x=n//2;return n+1 if n<2 else d(x)+d(~-x)+d(n+~x)
print(d(int(input()))%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
res = list()

for v in range(0, N+1):
    for a in range(0, N+1):
        b = v - a

        if b >= 0:
            u = a ^ b

            if 0 <= u <= N:
                res.append(('{}-{}'.format(u, v)))

print(len(set(res)))

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())
def nth_bit(d):
    return (n>>d)&1

dp = [[0,0,0] for _ in range(61)]
dp[-1][0] = 1
for d in range(59,-1,-1):
    for s in range(3):
        for k in range(3):
            s2 = min(2,2*s+nth_bit(d)-k)
            if s2>=0:
                dp[d][s2] += dp[d+1][s]
ans = sum(dp[0])%mod
print(ans)

Submission status: Accepted

Solution code:
def solve(n: int) -> int:
    mod = 1e9 + 7
    n_bin = '0' + bin(n)[2:]

    dp = [[0, 0, 0] for _ in range(len(n_bin))]
    dp[-1][0] = 1
    for i in range(len(n_bin) - 2, -1, -1):
        for s in range(3):
            for k in range(3):
                s2 = min(2, 2 * s + int(n_bin[len(n_bin) - i - 1]) - k)
                if s2 >= 0:
                    dp[i][s2] = int((dp[i][s2] + dp[i + 1][s]) % mod)

    return int(sum(dp[0]) % mod)

n = int(input())
print(solve(n))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

def main():
    N = int(input())
    """
    (u, v)での数え上げを(a, b)への数え上げにすり替えることができる。
    (a, b)->(u, v)の対応は単射ではないが、実は
        「a, bのどれかのビットが(0, 1), (1, 0)で入れ替わっているようなものを同一視」
    することでこの対応は単射になる。(すなわちa + b = c + d, a ^ b = c ^ dは
    a, bの各ビットを一部入れ替えたものがc, dになることに同値)

    なので問題は次のように言い変わる：
        「非負整数a, bでa + b <= Nなるものを数え上げよ。
        　ただしa, bの各ビットは(0, 0), (0, 1), (1, 1)の３パターンに限る。」
    これは桁DPをすれば良いが、単純に上の桁からやると繰り上げ処理が扱えない。

    そこでNよりどれだけ小さいかの情報もdpデーブルに持たせる。
        dp[i][j] = (上から0~i桁目まで見たとき値がN - jであるものの個数)
    これによる遷移はiに応じて異なるものの(jに-0, -2^i, -2^{i+1}のどれかが実行される)
    一応解ける。しかし計算量的にはまだ厳しい。

    そもそも計算量が大きい原因は遷移幅が大きすぎるから。そこでキーの持ち方を
        dp[i][j] = (上から0~i桁目まで見たとき(v >> i) = (N >> i) - j)
    と定める。こうすればNのiビット目とa, bのiビット目を見比べて上とほぼ同様に
    dp計算が可能でかつdpテーブルはだいぶ密になる。さらにdp[i + 1][j]でj >= 2の時は
    a, bのiビット目をどう取っても差が2^i以下に縮まることはないため遷移をまとめることができる。

    気持ちとしては上位ビットから考えるんだけど差分はmod 2^iで考えることで差分を0,1,2以上（繰り上がりケース）
    に限定して、(i+1)->iの遷移時に差分が増加するからそれをa, bのビットを選んで差分を抑制するか増大したまま
    放置するかを考えるイメージ。

    それにしても繰り上がりケースをまとめて考えていいのは数式的には明らかだけど、実際に遷移を考える際には
    妙に偶然感があって不思議な感じ。
    """
    n = bin(N)[2:]
    dp = [1, 1, 0]
    for i, c in enumerate(n):
        if i == 0: continue
        if c == '0':
            # dp[0] = (元々差がなくてiビット目が共に0か、元々差が2^(i+1)あって、iビット目が共に1)
            # dp[1] = (元々差が2^(i+1)あってiビット目が0と1)
            # dp[2] = (元々差が2^(i+1)あってiビット目が共に0か、元々差が2^(i+2)以上ある)
            dp = [dp[0] + dp[1], dp[1], dp[1] + dp[2] * 3]
        else:
            # dp[0] = (元々差がなくてiビット目が0と1)
            # dp[1] = (元々差がなくてiビット目が共に0か、元々差が2^(i+1)あってiビット目は共に1)
            # dp[2] = (元々差が2^(i+1)あってiビット目が0,0か0,1、もしくは元々差が2^(i+2)以上ある)
            dp = [dp[0], dp[0] + dp[1], dp[1] * 2 + dp[2] * 3]
        dp = [dp[0] % mod, dp[1] % mod, dp[2] % mod]
    print(sum(dp) % mod)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9+7
dp = [[0]*3 for _ in range(61)]
dp[60][0] = 1
for d in range(59,-1,-1):
  for s in range(3):
    for k in range(3):
      ns = min(2, 2*s + ((N>>d)&1) - k)
      if ns < 0:
        continue
      dp[d][ns] += dp[d+1][s]
      dp[d][ns] %= MOD

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

Submission status: Accepted

Solution code:
from functools import lru_cache
 
 
@lru_cache(None)
def f(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    elif n % 2 == 0:
        return (2 * f(n // 2 - 1) + f(n // 2)) % 1000000007
    else:
        return (2 * f(n // 2) + f(n // 2 - 1)) % 1000000007
 
 
n = int(input())
print(f(n))

Submission status: Accepted

Solution code:
N = int(input())
MOD = 10**9+7
dp = [[0]*3 for _ in range(61)]
dp[60][0] = 1
for d in range(59,-1,-1):
    for s in range(3):
        for k in range(3):
            ns = min(2, 2*s + ((N>>d)&1) - k)
            if ns < 0: continue
            dp[d][ns] += dp[d+1][s]
            dp[d][ns] %= MOD
print(sum(dp[0]) % MOD)

Submission status: Accepted

Solution code:
MOD=10**9+7
N=int(input())

dp=[[0 for _ in range(3)] for _ in range(64)]
dp[63][0]=1

for d in range(62,-1,-1):
  b=(N>>d)&1 
  s=dp[d+1][:]
  dp[d][0]=dp[d+1][0]+(1^b)*dp[d+1][1] % MOD
  dp[d][1]=b*dp[d+1][0]+dp[d+1][1] % MOD
  dp[d][2]=(1+b)*dp[d+1][1]+3*dp[d+1][2] % MOD

print(sum(dp[0][:]) % MOD)

Submission status: Accepted

Solution code:
import sys

p=10**9+7
dthbit=lambda d,n: (n>>d)&1

def main(n):
    dp=[[0 for _ in range(3)] for _ in range(64)]
    dp[63][0]=1
    for d in range(62,-1,-1):
        b=dthbit(d,n)
        s=dp[d+1][:]
        dp[d][0]=dp[d+1][0]+(1^b)*dp[d+1][1] % p
        dp[d][1]=b*dp[d+1][0]+dp[d+1][1] % p
        dp[d][2]=(1+b)*dp[d+1][1]+3*dp[d+1][2] % p
    return sum(dp[0][:]) % p

n=int(input())
print(main(n))

Submission status: Accepted

Solution code:
mod=10**9+7
def solve(n):
    if n==0:
        return 1
    res=0
    if n%2==1:
        temp=solve(n//2)
        res+=2*temp
        if n>=2:
            res+=temp-exact(n//2)
        return res%mod
    else:
        temp=solve(n//2)
        res+=temp
        res+=(temp-exact(n//2))*2
        return res%mod

def exact(n):
    if n==0:
        return 1
    m=n.bit_length()
    dp=[[0 for i in range(3)] for j in range(m)]
    dp[0][0]=1
    dp[0][1]=int(n%2==0)
    for i in range(1,m):
        for j in range(3):
            if j==0:
                if n>>i &1==1:
                    dp[i][j]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod
                else:
                    dp[i][j]=dp[i-1][0]
            elif j==1:
                if n>>i &1==1:
                    dp[i][j]=(dp[i-1][1]+dp[i-1][2])%mod
                else:
                    dp[i][j]=dp[i-1][0]
            elif j==2:
                if n>>i&1==1:
                    dp[i][j]=0
                else:
                    dp[i][j]=(dp[i-1][1]+dp[i-1][2])%mod
    return dp[-1][0]

N=int(input())
print(solve(N))

Submission status: Accepted

Solution code:
mod=10**9+7

memo={0:1}
def solve(n):
    if n in memo:
        return memo[n]
    res=0
    if n%2==1:
        res+=2*solve(n//2)
        if n>=2:
            res+=solve(n//2-1)
        memo[n]=0
        memo[n]=res%mod
        return res%mod
    else:
        res+=solve(n//2)
        res+=solve((n-1)//2)*(1+(n>=2))
        memo[n]=0
        memo[n]=res%mod
        return res%mod

print(solve(int(input())))

Submission status: Accepted

Solution code:
n = int(input())
x = n.bit_length()
dp = [[0]*3 for i in range(x)]
dp[-1][0] = 1
dp[-1][1] = 1
mod = 10**9+7

for i in range(x-2,-1,-1):

    if (n >> i) & 1:
        dp[i][0] = (dp[i+1][0])%mod
        dp[i][1] = (dp[i+1][0]+dp[i+1][1])%mod
        dp[i][2] = (dp[i+1][2]*3+dp[i+1][1]*2)%mod

    else:
        dp[i][0] = (dp[i+1][0]+dp[i+1][1])%mod
        dp[i][1] = (dp[i+1][1])%mod
        dp[i][2] = (dp[i+1][2]*3+dp[i+1][1])%mod
print(sum(dp[0])%mod)

Submission status: Accepted

Solution code:
from functools import lru_cache


@lru_cache(None)
def f(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    elif n % 2 == 0:
        return (2 * f(n // 2 - 1) + f(n // 2)) % 1000000007
    else:
        return (2 * f(n // 2) + f(n // 2 - 1)) % 1000000007


n = int(input())
print(f(n))

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
M = len(bin(N)) - 2
L = bin(N)[2:]

dp = [[0] * 3 for _ in range(M + 1)]
dp[0][0] = 1

for i in range(M):
    if L[i] == '1':
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][0] + dp[i][1]
        dp[i + 1][2] += 2 * dp[i][1] + 3 * dp[i][2]
    else:
        dp[i + 1][0] += dp[i][0] + dp[i][1]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][1] + 3 * dp[i][2]
    
    for j in range(3):
        dp[i + 1][j] %= MOD


print(sum(dp[M]) % MOD)

Submission status: Accepted

Solution code:
# solution

data= int(input())

array = format(data,"b")

mod = 1000000007

dynamic = [[0 for j in range(3)] for i in range(len(array)+1)]
dynamic[0][0] = 1

for i in range(len(array)):
  for j in range(3):
      for x in range(2):
        for y in range(x,2):
          b=(data>>i)&1
          dynamic[i+1][(x+y+j-b+1)//2] = (dynamic[i+1][(x+y+j-b+1)//2]+dynamic[i][j])%mod
print(dynamic[len(array)][0])

Submission status: Accepted

Solution code:
import sys

in1 = sys.stdin.readlines()
N = int(in1[0])
#N = 10 ** 18
#N = 2
"""
0 + 0 = 0
0 x 0 = 0

1 + 0 = 1
1 x 0 = 1

2 + 0 = 2
2 x 0 = 2
1 + 1 = 2
1 x 1 = 0

3 + 0 = 3
3 x 0 = 3
2 + 1 = 3
2 x 1 = 3
"""
p = 10 ** 9 + 7

def f(n):
    if n in d:
        return d[n]
    d[n] = f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)
    return d[n]

d = {0: 1, 1: 2}
print(f(N) % p)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)

    def get(self, init=None):
        if self.v is None:
            return init
        else:
            return self.v


def main():
    N = format(int(input()), "b")
    D = len(str(N))
    dp = [[0 for _ in range(3)] for __ in range(D + 1)]

    dp[0][0] = 1
    for d in range(D):
        for k in range(3):
            for s in range(3):
                sd = 2 * s + int(N[d]) - k
                if sd > 2:
                    sd = 2
                if sd < 0:
                    continue
                dp[d + 1][sd] += dp[d][s]
                dp[d + 1][sd] %= mod

    print(sum(dp[D]) % mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
mod=10**9+7
bt=bin(n)[2:]
k=len(bt)
dp=[[0]*2 for i in range(k+1)]
dp[0][0]=1
dp[0][1]=1
for i in range(k):
  j=int(bt[k-i-1])
  a,b,c=[(1,0,0),(1,1,0)][j]
  d,e,f=[(1,1,1),(0,1,2)][j]
  dp[i+1][0]=(a*dp[i][0]+b*dp[i][1]+c*(3**i))%mod
  dp[i+1][1]=(d*dp[i][0]+e*dp[i][1]+f*(3**i))%mod
print(dp[k][0])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def f(x, s):
    if min(x, s) < 0: return 0
    if max(x, s) < 2:
        if x and s: return 2
        else: return 1
    if (x, s) in memo: return memo[x, s]
    res = f(x >> 1, s >> 1) + f(x - 1 >> 1, s - 1 >> 1) + f(x >> 1, s - 2 >> 1)
    res = memo[x, s] = res % md
    return res

memo = {}
md = 10 ** 9 + 7

def main():
    n = II()
    print(f(n, n))

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
N = int(input())

MOD = 1000000007
cache = {0: 1, 1: 2}


def f(n):
    if n in cache:
        return cache[n]
    if n % 2 == 0:
        result = 2 * f(n // 2 - 1) + f(n // 2)
    else:
        result = f(n // 2 - 1) + 2 * f(n // 2)
    result %= MOD
    cache[n] = result
    return result


print(f(N))

Submission status: Accepted

Solution code:
cache = {}
M = 10**9+7
def f(i):
    if i == 0: return 0
    if i == 1: return 1
    if i in cache: return cache[i]
    k = i//2
    if i % 2 == 0: cache[i] = 2*f(k)%M + f(k-1)%M
    else: cache[i] = 2*f(k)%M + f(k+1)%M
    cache[i] %= M
    return cache[i]
print(f(int(input())+1))