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

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])%(10**9+7))

Submission status: Accepted

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 = ni()
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: Accepted

Solution code:
# coding: utf-8
# Your code here!
dic_memo={0:1,1:2}
M=10**9+7
def memo(N):
    if N in dic_memo:
        return dic_memo[N]
    dic_memo[N]=(memo((N-1)//2)+memo(N//2)+memo(N//2-1))%M
    return dic_memo[N]

n=int(input())
print(memo(n))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
odd={0:1}
even={0:1,1:3}
M=10**9+7
def memo(N):
    if N ==0:
        return 1
    if N==1:
        return 2
    return (memoodd((N-1)//2)+memoeven(N//2))%M

def memoodd(N):
    if N in odd:
        return odd[N]
    odd[N] = memo(N)
    return odd[N]

def memoeven(N):
    if N in even:
        return even[N]
    even[N] = (memo(N)+memo(N-1))%M
    return even[N]

n=int(input())
print(memo(n))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
odd={0:1}
even={0:1,1:3}
M=10**9+7
def memo(N):
    if N ==0:
        return 1
    if N==1:
        return 2
    return (memoodd((N-1)//2)+memoeven(N//2))%M


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))%M
    return even[N]

n=int(input())

print(memo(n))

Submission status: Accepted

Solution code:
n= int(input())
a = format(n,"b")
mod = 1000000007
dp = [[0 for j in range(3)] for i in range(len(a)+1)]
dp[0][0] = 1
for i in range(len(a)):
  for j in range(3):
      for x in range(2):
        for y in range(x,2):
          b=(n>>i)&1
          dp[i+1][(x+y+j-b+1)//2] = (dp[i+1][(x+y+j-b+1)//2]+dp[i][j])%mod
print(dp[len(a)][0])

Submission status: Accepted

Solution code:
def d_xor_sum(N):
    from functools import lru_cache

    @lru_cache()
    def f(k):
        # a+b<=k,a xor b <= k を満たす正整数(a,b)の組の個数(ただしa>=b)
        # N=0のとき(u,v)の組は(0,0)の1通り
        # N=1のとき(0,0),(1,1)の2通り
        return (1, 2)[k] if k <= 1 else f(k // 2) + f((k - 1) // 2) + f((k - 2) // 2)

    ans = f(N) % (10**9 + 7)
    return ans

N = int(input())
print(d_xor_sum(N))

Submission status: Accepted

Solution code:
MOD = 10**9+7

n = int(input())
s = bin(n)[2:]
l = len(s)
dp = [[0]*4 for i in range(l+1)]
dp[0][0] = 1

for i in range(l):
    b = 1 if s[i] == '1' else 0
    for j in range(4):
        for k in range(3):
            lj = min((j<<1) + b - k, 3)
            if 0 <= lj:
                dp[i+1][lj] += dp[i][j]
                dp[i+1][lj] %= MOD

# print(dp)
print(sum(dp[l])%MOD)

Submission status: Accepted

Solution code:
N=input()

memo={}
memo[0]=1
memo[1]=2

def func(N):
	if N in memo:
		return memo[N]
	result= ( func(N/2)+func((N-1)/2)+func(N/2-1) )% (10**9+7)
	
	memo[N]=result
	return result

print func(N)

Submission status: Accepted

Solution code:
def d_XorSum(N):
    MOD = 10**9 + 7
    memo = {0: 1, 1: 2}
    # N=0のとき(u,v)の組は(0,0)の1通り
    # N=1のとき(0,0),(1,1)の2通り

    def f(k):
        # a+b<=k,a xor b <= k を満たす正整数(a,b)の組の個数(ただしa>=b)
        if k in memo:
            return memo[k]
        ret = (f(k // 2) + f((k - 1) // 2) + f((k - 2) // 2)) % MOD
        memo[k] = ret
        return ret
    return f(N)

N = int(input())
print(d_XorSum(N))

Submission status: Accepted

Solution code:
N = int(input())
s = bin(N)[2:]
n = len(s)
dp = [[0] * 4 for i in range(len(s)+1)]
dp[0][0] = 1
MOD = int(1e9) + 7
for i in range(n):
    b = 1 if s[i] == '1' else 0
    for j in range(4):
        for k in range(3):
            nj = min(((j << 1) + b - k, 3))
            if 0 <= nj:
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
print(sum(dp[n]) % MOD)

Submission status: Accepted

Solution code:
N = int(input())
dp = [[0] * 3 for i in range(100)]

MOD = int(1e9+7)
maxBit = 70
while not (N >> maxBit):
    maxBit -= 1

dp[maxBit][0] = 1
dp[maxBit][1] = 1
for i in range(maxBit-1, -1, -1):
    for j in range(3):
        bit = (N >> i) & 1
        for k in range(3):
            nj = 2 * j + bit - k
            if nj < 0:
                continue
            nj = min((nj, 2))
            dp[i][nj] += dp[i+1][j]
            dp[i][nj] %= MOD

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

Submission status: Accepted

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

dp = [1,0,0]
for i in range(64,-1,-1):
    ndp = [0,0,0]
    for d in range(3):
        nd = d*2 + (n>>i&1)
        ndp[min(2,nd)] += dp[d] # 0,0
        if nd >= 1: ndp[min(2,nd-1)] += dp[d] # 0,1
        if nd >= 2: ndp[min(2,nd-2)] += dp[d] # 1,1
    dp = ndp
    
print(sum(dp) % MOD)

Submission status: Accepted

Solution code:
from functools import*
@lru_cache(None)
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: Accepted

Solution code:
from functools import*
@lru_cache(maxsize=None)
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: Runtime Error

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: Runtime Error

Solution code:
import sys

in1 = sys.stdin.readlines()
N = 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: Runtime Error

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))+1
    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: Runtime Error

Solution code:
n  = int(input())
m  = 10 ** 9 + 7
l  = 2 ** 32
xs = [int(x) for x in input().split()]
r  = 0

for i in range(0, n - 1):
	for j in range(i + 1, n):
		r = (r + ((xs[i] ^ xs[j]) % l)) % m

print(r)

Submission status: Runtime Error

Solution code:
n  = int(input())
m  = 10 ** 9 + 7
l  = 2 ** 32
xs = [int(x) for x in input().split()]
r  = 0

for i in range(0, n - 1):
	for j in range(i + 1, n):
		r = (r + ((xs[i] ^ xs[j])) % l) % m

print(r)

Submission status: Runtime Error

Solution code:
#include<cstdio>

const long A = 1e9 + 7;
long n;
int dp[2][3];

int main() {
    scanf("%ld", &n);
    dp[0][0] = 1;
    for (int i = 59; i >= 0; i--) {
        if ((n >> i) & 1) {
            dp[i & 1][2] = (static_cast<long>(dp[(i + 1) & 1][2]) * 3 + dp[(i + 1) & 1][1] * 2) % A;
            dp[i & 1][1] = (dp[(i + 1) & 1][1] + dp[(i + 1) & 1][0]) % A;
            dp[i & 1][0] = dp[(i + 1) & 1][0];
        }
        else {
            dp[i & 1][2] = (static_cast<long>(dp[(i + 1) & 1][2]) * 3 + dp[(i + 1) & 1][1]) % A;
            dp[i & 1][1] = dp[(i + 1) & 1][1];
            dp[i & 1][0] = (dp[(i + 1) & 1][1] + dp[(i + 1) & 1][0]) % A;
        }
    }
    
    int ans = 0;
    for (int i = 0; i <= 2; i++) ans = (ans + dp[0][i]) % A;
    printf("%d\n", ans);
}

Submission status: Runtime Error

Solution code:
import heapq

def dijkstra(m, s, t):
    INF = 1e10
    D = [INF] * N
    D[s] = 0
    Q = [(0 if s == v else INF, v) for v in range(N)]
    heapq.heapify(Q)

    while Q:
        c, u = heapq.heappop(Q)
        if D[u] < c:
            continue
        for v, w in m[u]:
            if D[v] > D[u] + w:
                D[v] = D[u] + w
                heapq.heappush(Q, (D[u]+w, v))
    return D[t] 

N, M = map(int, input().split())

# N < 100
m = [[] for i in range(N)]
E = [0] * M
for i in range(M):
    a, b, w = map(int, input().split())
    E[i] = a-1, b-1, w
    m[a-1].append((b-1,w))
    m[b-1].append((a-1,w))

count = 0
for a, b, w in E:
    d = dijkstra(m, a, b)
    #print((a+1, b+1), d, "w=%d"%w)
    if d < w:
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, K, L = map(int,  input().split())
mark = 0
U1 = UnionFind(N)
U2 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    U1.unite(p-1, q-1)
for i in range(L):
    r, s = map(int, input().split())
    U2.unite(r-1, s-1)
List=[]
for i in range(N):
    List.append((U1.par[i], U2.par[i], i))
List = sorted(List)
cnt = 0
member = []
ans = [0]*N
for i in range(N-1):
    if List[i][0]==List[i+1][0] and List[i][1]==List[i+1][1]:
        cnt+=1
        if member:
            member.append(List[i+1][2])
        else:
            member.append(List[i][2])
            member.append(List[i+1][2])
    else:
        for j in member:
            ans[j]=cnt
        cnt = 0
        member = []
for j in member:
            ans[j]=cnt
for i in range(N):
    print(ans[i]+1)

Submission status: Runtime Error

Solution code:
import numpy as np


def read_input():
    n = int(input())
    return n


def mymod(x):
    return x % (10**9 + 7)


def submit():
    N = read_input()
    N = list(map(int, list(bin(N)[2:])))

    dp = np.zeros((len(N) + 1, 3))
    dp[len(N)][0] = 1

    for i in range(len(N) - 1, -1, -1):
        for s in range(3):
            for k in range(3):
                new_s = 2 * s + N[len(N) - i - 1] - k
                if new_s < 0:
                    continue
                if new_s > 2:
                    new_s = 2
                dp[i][new_s] += mymod(dp[i + 1][s])
            dp[i][0] = mymod(dp[i][0])
            dp[i][1] = mymod(dp[i][1])
            dp[i][2] = mymod(dp[i][2])

    print(int(sum(dp[0])) % (10**9 + 7))

if __name__ == '__main__':
    submit()

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
N = int(input())
 
dp = [1,0,0]
for i in range(64,-1,-1):
  ndp = [0,0,0]
  for d in range(3):
    nd = d*2 + (n>>>i&1)
    ndp[min(2,nd)] += dp[d]
    if nd >= 1: ndp[min(2,nd-1)] += dp[d]
    if nd >= 2: ndp[min(2,nd-2)] += dp[d]
  dp = ndp
  
print(sum(dp) % MOD)

Submission status: Runtime Error

Solution code:
MOD = int(1e9) + 7
N = int(input())
 
dp = [1,0,0]
for i in range(64,-1,-1):
  ndp = [0,0,0]
  for d in range(3):
    nd = d*2 + (n>>>i&1)
    ndp[min(2,nd)] += dp[d]
    if nd >= 1: ndp[min(2,nd-1)] += dp[d]
    if nd >= 2: ndp[min(2,nd-2)] += dp[d]
  dp = ndp
  
print(sum(dp) % MOD)

Submission status: Runtime Error

Solution code:
MOD = int(1e9) + 7
N = int(input())
 
dp = [1,0,0]
for i in range(64,-1,-1):
  ndp = [0,0,0]
  for d in range(3):
    nd = d*2 + (N>>>i&1)
    ndp[min(2,nd)] += dp[d]
    if nd >= 1: ndp[min(2,nd-1)] += dp[d]
    if nd >= 2: ndp[min(2,nd-2)] += dp[d]
  dp = ndp
  
print(sum(dp) % MOD)

Submission status: Runtime Error

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

dp[0][0] = 1
for i in range(64,-1,-1):
  ndp = [0,0,0]
  for d in range(3):
    nd = d*2 + (N>>>i&1)
    ndp[min(2,nd)] += dp[d]
    if nd >= 1: ndp[min(2,nd-1)] += dp[d]
    if nd >= 2: ndp[min(2,nd-2)] += dp[d]
  dp = ndp
  
print(sum(dp) % MOD)

Submission status: Runtime Error

Solution code:
MOD = int(1e9) + 7
N = int(input())
dp[0][0] = 1
for i in range(64,-1,-1):
  ndp[0][0] = 0
  for d in range(3):
    nd = d*2 + (N>>>i&1)
    ndp[min(2,nd)] += dp[d]
    if nd >= 1: ndp[min(2,nd-1)] += dp[d]
    if nd >= 2: ndp[min(2,nd-2)] += dp[d]
  dp = ndp
print(sum(dp) % MOD)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
Nc = 1
e = 0
for i in range(N):
    if (N-A[i]-1) < 0:
        e = 1
        Nc = 0
        break
if e ==0:
    if A.count(0) >= 2:
        Nc *= 0
    else:
        for i in range(N-1):
                if A.count(i+1) == 2:
                    Nc *= 2
                elif A.count(i+1) ==0:
                    Nc *= 1
                else:
                    Nc *= 0
                    break

print(Nc%1000000007)

Submission status: Runtime Error

Solution code:
from functools import*
@lru_cache
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))