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:
N= int(input())

import sys
sys.setrecursionlimit(10000)

bit = bin(N)[2:]

dp = [[0] * 9 for i in range(len(bit) + 1)]

def aaa(bit, k):
    
    res = 0
    for i in range(9):
        a = i // 3
        b = i % 3
        if (int(bit[0]) -b) + (k -a) *2 >= 2:
            res += 3**(len(bit) - 1) % 1000000007
        elif (int(bit[0]) -b) + (k -a) *2 < 0:
            pass
        else:
            if len(bit) > 1:
                res += aaa(bit[1:], (int(bit[0]) -b) + (k -a) *2)
            else:
                res += 1
    print(bit, k, res)
    return res

print(aaa(bit, 0))

Submission status: Wrong Answer

Solution code:
#N = int(raw_input())
N = 1422
bitlen = len(bin(N))-2
MOD = 10**9 + 7
dp = [[0 for i in range(N+1)] for j in range(bitlen + 1)]
dp[bitlen][0] = 1
for i in range(bitlen, 0, -1):
	for j in range(N+1):
		if dp[i][j] > 0:
			test = 1 << (i-1)
			dp[i-1][j] += dp[i][j]
			if j+test <= N:
				dp[i-1][j+test] += dp[i][j]
				if j+2*test <= N:
					dp[i-1][j+2*test] += dp[i][j]
print(sum(dp[0]) % MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = 0
for i in range(N):
    tmp = 1
    b = 1
    while b <= i:
        if i & b > 0:
            tmp <<= 1
        b <<= 1
    tmp >>= 1
    ans = (ans + tmp) % 10000000007

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
n = int(input())

m = [0, 1]
for i in range(1, (n - 1) // 2 + 2):
    m.append(m[i])
    m.append((m[i] + m[i + 1]) % MOD)

if n % 2 == 1:
    print('pop')
    m.pop()

print(sum(m) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007
n = int(input())

m = [0, 1]
for i in range(1, (n - 1) // 2 + 2):
    m.append(m[i])
    m.append((m[i] + m[i + 1]) % MOD)

if n % 2 == 1:
    m.pop()

print(sum(m) % MOD)

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:
n = int(input())
mod = 10**9 + 7

n_bit = []
x = n
while(x>0):
    n_bit.append(x%2)
    x //= 2
n_bit = n_bit[::-1]

n_len = len(n_bit)

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

for i,bi in enumerate(n_bit):
    if(bi == 0):
        dp[i+1][0] += dp[i][0] + dp[i][1]
        dp[i+1][1] += dp[i][1]
        dp[i+1][2] += dp[i][1] + dp[i][2]*3
    else:
        dp[i+1][0] += dp[i][0]
        dp[i+1][1] += dp[i][0] + dp[i][1]
        dp[i+1][2] += dp[i][1]*2 + dp[i][2]*3
    dp[i+1][0] %= mod
    dp[i+1][1] %= mod
    dp[i+1][2] %= mod

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

Submission status: Accepted

Solution code:
n=int(input())
d=dict()
def get(n):
    if(n==1):return 1
    if(n==0):return 0
    if(n in d.keys()):return d[n]
    if(n%2==0):
        d[n]=2*get(n//2)+get(n//2-1)
    else:
        d[n]=2*get(n//2)+get(n//2+1)
    d[n]%=(10**9+7)
    return d[n]
def check(u,v,n):
    for a in range(n+1):
        b=u ^ a
        if(a+b==v):
            return 1
    return 0
#for e in range(1,n):
#    ans=0
#    for i in range(e+1):
##        for j in range(e+1):
#            ans+=check(i,j,e)
#    print(ans,get(e+1))
print(get(n+1))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,read().split())

d = {}


"""
res = [[0]*100 for _ in range(100)]
for i in range(128):
    for j in range(128):
        u = i^j
        v = i+j
        if u<100 and v<100: res[u][v] = 1

x = 0
for i in range(n+1):
    for j in range(n+1):
        x += res[i][j]

for i in res[:10]:
    print(i[:10])

for i in range(100):
    for j in range(1,100):
        res[i][j] += res[i][j-1]
for i in range(1,100):
    for j in range(100):
        res[i][j] += res[i-1][j]

#for i in res[:10]:
#    print(i[:10])
"""



def f(n,m):
    if (n,m) in d: return d[(n,m)]
    if n<0 or m<0:
        return 0
    if n==0:
        return max(1+n//2,1+m//2)
    if m==0:
        return 1

    nn = n>>1 if n&1 else (n>>1)-1
    mm = m>>1 if m&1 else (m>>1)-1
    
    
    #print(f"({n},{m})", f(nn,mm),f(n>>1,m>>1),f(n>>1,(m>>1)-1))    
    v =  f(nn,mm) + f(n>>1,m>>1) + f(n>>1,(m>>1)-1)
    d[(n,m)] = v
    #assert v == res[n][m]
    return v

ans = f(n,n)
print(ans%(10**9+7))

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
from collections import Counter
readline = sys.stdin.readline
MOD = 10**9+7
N = int(readline())

CC = Counter()
CC[0] = 1
CC[1] = 2
def calc(x):
    res = 0
    if CC[x]:
        res = CC[x]
    elif x == 1:
        res = 2
    elif x%2 == 0:
        res = 2*calc(x//2-1) + calc(x//2)
    else:
        res = 2*calc(x//2) + calc(x//2-1)
    CC[x] = res%MOD
    return res%MOD
print(calc(N))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 10 ** 9 + 7


n  = bin(I())[2:]
dp0, dp1, dp2 = 1, 0, 0
for d in n:
    if d == '1':
        dp0, dp1, dp2 = dp0 % mod, (dp0 + dp1) % mod, (dp1 * 2 + dp2 * 3) % mod
    else:
        dp0, dp1, dp2 = (dp0 + dp1) % mod, dp1 % mod, (dp1 + dp2 * 3) % mod



print((dp0 + dp1 + dp2) % mod)

Submission status: Accepted

Solution code:
tg = 0
ls = 1
md = 2
MOD = 10**9+7
n = int(input())
l = n.bit_length()
# ^tight/loose, +tight/loose/middle, bitnum
dp = [[[0] * l for _ in range(3)] for i in range(2)]
for i in range(l):
    if i == 0:
        # 10
        dp[tg][tg][0] = 1
        # 00
        dp[ls][md][0] = 1
        continue
    # i-th bit is 1
    if n & (1 << l - i - 1):
        # 10
        dp[tg][tg][i] += dp[tg][tg][i-1]
        dp[ls][ls][i] += dp[ls][md][i-1]
        dp[ls][tg][i] += dp[ls][tg][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
        # 00
        dp[ls][md][i] += dp[tg][tg][i-1]
        dp[ls][ls][i] += dp[ls][md][i-1]
        dp[ls][md][i] += dp[ls][tg][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
        # 11 
        dp[ls][md][i] += dp[ls][md][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
    # i-th bit is 0
    else:
        # 10
        dp[ls][ls][i] += dp[ls][ls][i-1]
        dp[ls][md][i] += dp[ls][md][i-1]
        # 00
        dp[tg][tg][i] += dp[tg][tg][i-1]
        dp[ls][ls][i] += dp[ls][md][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
        dp[ls][tg][i] += dp[ls][tg][i-1]
        # 11 
        dp[ls][tg][i] += dp[ls][md][i-1]
        dp[ls][ls][i] += dp[ls][ls][i-1]
    for xp in dp:
        for pp in xp:
            pp[i] %= MOD

ans = 0
for xp in dp:
    for pp in xp:
        ans += pp[-1]
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
b = bin(n)[2:]
MOD = 10 ** 9 + 7

dp1, dp2, dp3 = 1, 0, 0

for d in b:
    if d == '1':
        dp1, dp2, dp3 = dp1 % MOD, (dp1 + dp2) % MOD, (dp2 * 2 + dp3 * 3) % MOD
    else:
        dp1, dp2, dp3 = (dp1 + dp2) % MOD, dp2, (dp2 + dp3 * 3) % MOD

print((dp1 + dp2 + dp3) % MOD)

Submission status: Accepted

Solution code:
#社協

N = int(input())
binN = format(N, "b").zfill(60)
mod = 7 + 10 ** 9

DP = [[0, 0, 0] for _ in range(60)]
if binN[0] == "0":
    DP[0] = [1, 0, 0]
else:
    DP[0] = [1, 1, 0]

for i in range(1, 60):   
    if binN[i] == "0":
        DP[i][0] = (DP[i-1][0] + DP[i-1][1]) % mod
        DP[i][1] = DP[i-1][1]
        DP[i][2] = (DP[i-1][2] * 3 + DP[i-1][1]) % mod
    else:
        DP[i][0] = DP[i-1][0]
        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
print(sum(DP[-1]) % mod)

Submission status: Accepted

Solution code:
N = int(input())
binN = format(N, "b").zfill(60)
mod = 7 + 10 ** 9

DP = [[0, 0, 0] for _ in range(60)]
if binN[0] == "0":
    DP[0] = [1, 0, 0]
else:
    DP[0] = [1, 1, 0]

for i in range(1, 60):   
    if binN[i] == "0":
        DP[i][0] = (DP[i-1][0] + DP[i-1][1]) % mod
        DP[i][1] = DP[i-1][1]
        DP[i][2] = (DP[i-1][2] * 3 + DP[i-1][1]) % mod
    else:
        DP[i][0] = DP[i-1][0]
        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
print(sum(DP[-1]) % mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
n = int(input())
dp = [[0 for _ in range(3)] for _ in range(61)]
dp[60][0] = 1
for i in range(59, -1, -1):
	if (n>>i)&1 == 1:
		dp[i][0] += dp[i+1][0]
		dp[i][1] += dp[i+1][0] + dp[i+1][1]
		dp[i][2] += 2*dp[i+1][1] + 3*dp[i+1][2]
	else:
		dp[i][0] += dp[i+1][0] + dp[i+1][1]
		dp[i][1] += dp[i+1][1]
		dp[i][2] += dp[i+1][1] + 3*dp[i+1][2]
	for j in range(3):
		dp[i][j] %= MOD
print(sum(dp[0])%MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy

MOD = 10 ** 9 + 7
IMAX = 200
JMAX = 2

def dp(n):
    dp = [0 for j in range(JMAX + 1)]
    dp[0] = 1
    for i in reversed(range(IMAX + 1)):
        pre = deepcopy(dp)
        dp[2] += pre[1]
        dp[2] += 2 * pre[2]
        d = ((1 << i) & n) >> i
        if d:
            dp[1] += pre[0]
            dp[2] += pre[1]
        else:
            dp[0] += pre[1]
        dp = take_mod(dp)
    return sum(dp) % MOD

def take_mod(dp):
    res = [x % MOD for x in dp]
    return res

def main():
    n = int(input())
    print(dp(n))

main()

Submission status: Accepted

Solution code:
N= int(input())
bit = bin(N)[2:]
k = len(bit)
dp = [[0] * 2 for i in range(len(bit) + 1)]
dp[0][0] = 1
dp[0][1] = 1
for i in range(k):
	j = int(bit[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) % 1000000007
	dp[i+1][1] = d * dp[i][0] + e * dp[i][1] + f * 3**i % 1000000007

print(dp[k][0])

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

N = int(input())

binN = list(map(int, bin(N)[2:]))
dp = [[0] * 3 for _ in range(len(binN) + 1)]
dp[0][0] = 1
for i, Ni in enumerate(binN):
    dp[i + 1][0] += dp[i][0] * 1
    dp[i + 1][1] += dp[i][0] * Ni
    dp[i + 1][0] += dp[i][1] * (1 - Ni)
    dp[i + 1][1] += dp[i][1] * 1
    dp[i + 1][2] += dp[i][1] * (1 + Ni)
    dp[i + 1][2] += dp[i][2] * 3
    dp[i + 1][0] %= MOD
    dp[i + 1][1] %= MOD
    dp[i + 1][2] %= MOD

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

n = input()
n = bin(n)[2:]

def func(dig, val1, val2):
    for i in range(dig):
        v1 = val1 * 2 + val2
        v2 = val2 * 2 + val1
        val1, val2 = v1, v2
    return val2

ans = 0
val1 = 0
val2 = 1
for i in range(len(n)):
    if n[i] == '1':
        ans += func(len(n) - i - 1, val1, val1 + val2)
        val1 = val1 + val2
    else:
        val2 = val1 + val2
print (ans + val2) % (10 ** 9 + 7)

Submission status: Accepted

Solution code:
def Dp(x, hl, islim):
    if x == len(digit):
        return hl == 0
    if f[x][hl][islim]:
        return f[x][hl][islim]
    ans = 0
    mx = int(digit[x]) if islim else 1
    for i in range(mx + 1):
        ans += Dp(x + 1, hl, islim and i == mx)
        if hl != i:
            ans += Dp(x + 1, not hl, islim and i == mx)
    ans %= p
    f[x][hl][islim] = ans
    return ans

p = 10**9 + 7
digit = bin(int(input()))[2:]
f = [[[0, 0], [0, 0]] for i in range(len(digit))]
print(Dp(0, 0, 1))

Submission status: Accepted

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

memo = {0: 1, 1: 2}
def S(k):
    if k in memo:
        return memo[k]
    if k % 2 == 1:
        result = (2*S(k/2) + S(k/2-1)) % MOD
    else:
        result = (S(k/2) + 2*S(k/2-1)) % MOD
    memo[k] = result
    return result
print S(N)

Submission status: Accepted

Solution code:
MOD = 10**9+7
d1 = {0: 1}
d2 = {0: 1, 1: 2}
def f(k):
    if k in d1:return d1[k]
    d1[k] = f(k/2) + (k%2<1 and f(k/2-1))
    return d1[k]
def s(k):
    if k in d2:return d2[k]
    d2[k] = (f(k) + s(k-1) if k%2 else s(k/2) + 2*s(k/2-1)) % MOD
    return d2[k]
print s(input())

Submission status: Runtime Error

Solution code:
    n,m,q = input().split(" ")
    n1=int(n/2)
    m1=(m/2)
    for i in range(int(q)):
        a,b,c,d = input().split(" ")
        a = int(a)
        b= int(b)
        c = int(c)
        d=int(d)
        if(a==1 and c==2):
            if((b<=n1 and d<=m1) or (b>n1 and d>m1)):
                print("YES")
            else:
                print("NO")
       if(a==2 and c==1):
            if((b<=m1 and d<=n1) or (b>m1 and d>n1)):
                print("YES")
            else:
                print("NO")
     if(a==1 and c==1):
            if((b<=n1 and d<=n1) or (b>n1 and d>n1)):
                print("YES")
            else:
                print("NO")
     if(a==2 and c==2):
            if((b<=m1 and d<=m1) or (b>m1 and d>m1)):
                print("YES")
            else:
                print("NO")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

MOD = 10 ** 9 + 7
IMAX = 70
JMAX = 10 ** 5

def dp(n):
    assert n <= JMAX
    dp = [0 for j in range(JMAX + 1)]
    dp[0] = 1
    for i in reversed(range(IMAX + 1)):
        d = 2 ** i
        for j in reversed(range(JMAX + 1)):
            if j - d >= 0:
                dp[j] += dp[j - d]
            if j - 2 * d >= 0:
                dp[j] += dp[j - 2 * d]
    return sum(dp[:n + 1])

def main():
    n = int(input())
    print(dp(n))

main()

Submission status: Runtime Error

Solution code:
N= int(input())

bit = bin(N)[2:]
k = len(bit)
dp = [[0] * 2 for i in range(len(bit) + 1)]
for i in range(k):
	j = int(bit[k-i+1])
	a,b,c = [(1,0,0),(1,1,0)][j]
	d,e,f = [(2, 1, 1),(1, 2, 2)][j]
	dp[i+1][0] = a * dp[i][0] + b * dp[i][1] + c * 3**i
	dp[i+1][1] = d * dp[i][0] + e * dp[i][1] + f * 3**i

print(dp[k][0])

Submission status: Runtime Error

Solution code:
N= int(input())

def b(N):
    if N < 2:
        res = N
    else:
        if N % 2 == 0:
            res = b(N//2)
        else:
            res = b( (N-1)//2 ) + b( (N+1)//2 )
    return res
def a(N):
    if N > 0:
        res = a(N-1)
    else:
        res = 0
    return res + b(N+1)

print(a(N))

Submission status: Runtime Error

Solution code:
N = int(raw_input())
#N = 1422
MOD = 10**9 + 7
l = [(a^b,a+b) for a in range(0,N+1) for b in range(a,N+1) if a+b <= N]
for u in range(0,N+1):
	for a in range(0,N+1):
s = set(l)
print(len(s) % MOD)