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())
s=bin(N)[2:]
K=len(s)
mod=10**9+7
#bp[i][j]は上からiビット以上が確定でN>>(K-i)-v>>(K-i)=jとなる通り数
bp=[[0]*(3) for i in range(K+1)]
bp[0][0]=1
for i in range(1,K+1):
    if s[i-1]=="0":
        bp[i][0]=(bp[i-1][1]+bp[i-1][0])%mod
        bp[i][1]=bp[i-1][1]
        bp[i][2]=(bp[i-1][1]+bp[i-1][2]*3)%mod
    else:
        bp[i][0]=bp[i-1][0]
        bp[i][1]=(bp[i-1][1]+bp[i-1][0])%mod
        bp[i][2]=(bp[i-1][1]*2+bp[i-1][2]*3)%mod
print(sum(bp[-1])%mod)

Submission status: Accepted

Solution code:

"""

a,bの組み合わせから u,vを作っていく
a,bが違うのに u,vが同じになるパターンはbit入れ替えのみ？

a1 ^ b1 == a2 ^ b2 とする
bit入れ替えでなく, 左右のabが等しくないとき、 00 と 11になっている
和にすると片方が片方より 2**[桁+1]大きい
→各桁について 2,4,8,16…の差が生まれるが、これらが相殺されることは無い。

よってabの各桁の組み合わせが (0,0)(0,1)(1,1)のどれかだけ調べればよい
u <= vより、vの条件だけ考えていく。


現時点でのNとの差が
0 * 2**(d+1) → (0,0)のみ設置可能
1 * 2**(d+1) → (0,0)(0,1)のみ設置可能
                (0,0) → 差は2 * (2**d)
2 *

(1,1)が来ると繰り上がってしまう。→ 2**(d+1)増える

dp[桁][乖離度]
"""
mod = 10**9+7
N = int(input())

NB = format(N,"b")

dp = [ [0]*3 for i in range(len(NB)) ]

dp[0][0] = 1
dp[0][1] = 1

for i in range(len(NB) - 1):

    if NB[i+1] == "0":
        #(0,0)を加える場合
        dp[i+1][0] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        #(0,1)を加える場合
        #dp[i][0]にはくわえられない
        dp[i+1][1] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        #(1,1)を加える場合
        dp[i+1][0] += dp[i][1]
        dp[i+1][2] += dp[i][2]

    else:
        
        #(0,0)を加える
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        #(0,1)
        dp[i+1][0] += dp[i][0]
        dp[i+1][2] += dp[i][1]
        dp[i+1][2] += dp[i][2]

        #(1,1)
        #dp[i][0]にはくわえられない
        dp[i+1][1] += dp[i][1]
        dp[i+1][2] += dp[i][2]

    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:
MOD=10**9+7
N = int(input())
K = len(bin(N)) - 2
DP = [[0]*3 for _ in range(K+1)]
DP[0][0] = 1
for k in range(K):
    if N & (1 << K - k - 1):
        DP[k+1][0] = DP[k][0]
        DP[k+1][1] = (DP[k][0] + DP[k][1]) % MOD
        DP[k+1][2] = (DP[k][1]*2 + DP[k][2]*3) % MOD
    else:
        DP[k+1][0] = (DP[k][0] + DP[k][1]) % MOD
        DP[k+1][1] = DP[k][1]
        DP[k+1][2] = (DP[k][1] + DP[k][2]*3) % MOD
print(sum(DP[-1]) % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
s = bin(n)[2:]
dp = [[0, 0, 0] for _ in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
    if s[i] == '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
    for j in range(3):
        dp[i+1][j] %= MOD
print(sum(dp[-1])%MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
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, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = float('INF')
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


n = I()
dp = [[0] * 3 for _ in range(62)]
dp[0][0] = 1
for i in range(61):
    zero, one, two = dp[i]
    if n >> (60 - i) & 1:
        zero, one, two = zero, zero + one, 2 * one + 3 * two
    else:
        zero, one, two = zero + one, one, one + 3 * two
    dp[i + 1] = [zero % mod, one % mod, two % mod]


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

Submission status: Accepted

Solution code:
N = int(input())
mod = 10**9+7
N = '{:060b}'.format(N)[::-1]

dp = [[[[-1 for _ in range(3)] 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]
    if b:
        res = f(n-1,1,1,2)+f(n-1,1,1,1)+f(n-1,1,1,0)
    else:
        if not a:
            if N[n]=='0':
                res = f(n-1,0,0,0)
            else:
                res = f(n-1,1,0,0)+f(n-1,0,0,1)
        else:
            if N[n]=='0':
                res = f(n-1,0,0,2)+f(n-1,1,0,1)+f(n-1,1,1,0)
            else:
                res = f(n-1,1,0,2)+f(n-1,1,1,1)+f(n-1,1,1,0)
    res %= mod
    dp[n][a][b][c] = res
    return res

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import lru_cache

mod = 10 ** 9 + 7

@lru_cache(maxsize=None)
def f(n):
    if n <= 1:
        return n + 1
    return (f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)) % mod

N = int(input())
print(f(N))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())

memo = {0:1, 1:2}
def f(n):
    if n not in memo:
        memo[n] = (f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)) % mod
    return memo[n]

print(f(N))

Submission status: Accepted

Solution code:
N = int(input())
a, b, c = 1, 0, 0
for i in range(80)[::-1]:
    if N>>i & 1: a, b, c = a, a+b, 2*b+3*c
    else: a, b, c = a+b, b, b+3*c
print((a+b+c) % (10**9+7))

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():
    n=int(input())
    dp=[1,0,0]
    for d in range(60,-1,-1):
        ndp=[0]*3
        nd=(n>>d)&1
        for s,ad,bd in product(range(3),range(2),range(2)):
            if(ad>bd): continue
            ns=min(2,2*s+nd-(ad+bd))
            if(ns<0): continue
            ndp[ns]+=dp[s]
            ndp[ns]%=MOD
        dp=ndp
    print(sum(dp)%MOD)    
resolve()

Submission status: Accepted

Solution code:
# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
N = int(input())

mod = 10**9+7
# bitも上から見ていくので逆順にして扱いやすくする
binN = format(N,"061b")[::-1]

dp = [[0,0,0] for _ in range(61)]
dp[60][0] = 1

for i in range(59,-1,-1):
    # i桁目のbitが 1
    if binN[i]=="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]
    # i桁目のbitが 0
    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((dp[0][0] + dp[0][1] + dp[0][2]) % mod)

Submission status: Accepted

Solution code:
mod = 10**9+7

n = int(input())
k = n.bit_length()

DP = [[0]*3 for i in range(k+1)]
DP[0][2] = 1
bit = [int(i) for i in bin(n)[2:]]
for i in range(k):
    DP[i+1][0] = 3*DP[i][0]
    if bit[i]:
        DP[i+1][1] += DP[i][1]
        DP[i+1][0] += 2*DP[i][1]
        DP[i+1][1] += DP[i][2]
        DP[i+1][2] += DP[i][2]
    else:
        DP[i+1][2] += DP[i][1]
        DP[i+1][1] += DP[i][1]
        DP[i+1][0] += DP[i][1]
        DP[i+1][2] += DP[i][2]

    for j in range(3):
        DP[i+1][j] %= mod

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
N = format(N, '060b')[::-1]
# N[i] := Nのiビット目としておく
N = [0] + list(map(int, N))

# dp[i][j] := iビット目まで見て、その桁までの値において、a+b がNより j*2^i 小さい通り数(j>=2はj=2で同一視)
dp = list2d(61, 3, 0)
dp[60][0] = 1
for i in range(60, 0, -1):
    # jの状態 j=0,1,2以上 の3通り
    for j in range(3):
        # 今回の桁でのa,bの選び方 (0,0)=0,(0,1)=1,(1,1)=2 の3通り
        for k in range(3):
            # 1桁下がる時に、現在のjは 2^i = 2*2^(i-1) から、*2される
            # Nのビットが立っている桁なら1を足す
            # 今回追加するk(0~2)を引く
            nxt = min(j*2 + N[i] - k, 2)
            # nxtがマイナスなら繰り上がりでNを超えるので遷移させない
            if nxt >= 0:
                dp[i-1][nxt] += dp[i][j]
                dp[i-1][nxt] %= MOD
print((dp[0][0]+dp[0][1]+dp[0][2])%MOD)

Submission status: Accepted

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

Solution code:
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(int(input()))%(10**9+7))

Submission status: Accepted

Solution code:
N = int(input())

d = {0: 1, 1: 2}

def f(n):
  if n in d:
    return d[n]
  d[n] = (f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)) % (10**9 + 7)
  return d[n]

print(f(N))

Submission status: Accepted

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)]
    dp[0][0] = 1
    for i in range(binmax):
        if (n >> binmax - i - 1) & 1:
            dp[i + 1][0] = dp[i][0] % mod
            dp[i + 1][1] = (dp[i][0] + dp[i][1]) % mod
            dp[i + 1][2] = (2 * dp[i][1] + 3 * dp[i][2]) % mod
        else:
            dp[i + 1][0] = (dp[i][0] + dp[i][1]) % mod
            dp[i + 1][1] = dp[i][1] % mod
            dp[i + 1][2] = (dp[i][1] + 3 * dp[i][2]) % mod
    print(sum(dp[binmax]) % mod)

    return


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

Submission status: Accepted

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)) - 1
    dp = [[0] * 3 for i in range(binmax)]
    dp[0][0] = 1
    for i in range(binmax - 1):
        if n & (1 << (binmax - 2 - i)):
            dp[i + 1][0] = dp[i][0] % mod
            dp[i + 1][1] = (dp[i][0] + dp[i][1]) % mod
            dp[i + 1][2] = (2 * dp[i][1] + 3 * dp[i][2]) % mod
        else:
            dp[i + 1][0] = (dp[i][0] + dp[i][1]) % mod
            dp[i + 1][1] = dp[i][1] % mod
            dp[i + 1][2] = (dp[i][1] + 3 * dp[i][2]) % mod
    print(sum(dp[binmax - 1]) % mod)

    return


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

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
N = int(sys.stdin.readline())

# # dp[i][j]: 右からiビット目まで決まってて、vがjとなるパターン数
# dp = [[0] * (N + 1) for _ in range(N.bit_length())]
# # 両方0
# dp[0][0] += 1
# # 片方1
# dp[0][1] += 1
# # 両方1
# dp[0][2] += 1
# for i in range(1, N.bit_length()):
#     for j in range(N + 1):
#         # 両方0
#         dp[i][j] += dp[i - 1][j]
#         # 片方1
#         if j + pow(2, i) <= N:
#             dp[i][j + pow(2, i)] += dp[i - 1][j]
#         # 両方1
#         if j + pow(2, i + 1) <= N:
#             dp[i][j + pow(2, i + 1)] += dp[i - 1][j]
# print(sum(dp[-1]))


# # dp[j]: vがjとなるパターン数
# # 上から決めてく
# dp = [0] * (N + 1)
# # 両方0
# dp[0] = 1
# # 片方1
# dp[1 << (N.bit_length() - 1)] = 1
# for i in reversed(range(N.bit_length() - 1)):
#     for j in reversed(range(N + 1)):
#         # 片方1
#         if j + pow(2, i) <= N:
#             dp[j + pow(2, i)] += dp[j]
#         # 両方1
#         if j + pow(2, i + 1) <= N:
#             dp[j + pow(2, i + 1)] += dp[j]
#     print(dp)
# print(sum(dp))


# # dp[i][j]: 右からiビット目まで決まってて、N-vがjとなるパターン数
# # 上から決めてく
# dp = [[0] * (N + 1) for _ in range(N.bit_length())]
# # 両方0
# dp[-1][-1] = 1
# # 片方1
# dp[-1][N - (1 << (N.bit_length() - 1))] = 1
# for i in reversed(range(N.bit_length() - 1)):
#     for j in reversed(range(N + 1)):
#         # 両方0
#         dp[i][j] += dp[i + 1][j]
#         # 片方1
#         if j - (1 << i) >= 0:
#             dp[i][j - (1 << i)] += dp[i + 1][j]
#         # 両方1
#         if j - (1 << i + 1) >= 0:
#             dp[i][j - (1 << i + 1)] += dp[i + 1][j]
#     print(dp)
# print(sum(dp[0]))

# # dp[i][j]: 右からiビット目まで決まってて、(N>>i)-(v>>i)がjとなるパターン数
# # 上から決めてく
# dp = [[0] * (N * 3) for _ in range(N.bit_length())]
# # 両方0
# dp[-1][1] = 1
# # 片方1
# dp[-1][0] = 1
# for i in reversed(range(N.bit_length() - 1)):
#     for j in reversed(range(N + 1)):
#         if N >> i & 1:
#             # 両方0
#             dp[i][(j << 1) + 1] += dp[i + 1][j]
#             # 片方1
#             dp[i][j << 1] += dp[i + 1][j]
#             if j > 0:
#                 # 両方1
#                 dp[i][(j << 1) - 1] += dp[i + 1][j]
#         else:
#             # 両方0
#             dp[i][j << 1] += dp[i + 1][j]
#             if j > 0:
#                 # 片方1
#                 dp[i][(j << 1) - 1] += dp[i + 1][j]
#                 # 両方1
#                 dp[i][(j << 1) - 2] += dp[i + 1][j]
#     print(dp)
# print(sum(dp[0]))

# dp[i][j]: 右からiビット目まで決まってて、(N>>i)-(v>>i)がjとなるパターン数
# j >= 2 以降は j <= 1 に入ってこないので j == 2 としてまとめる
# 上から決めてく
dp = [[0] * 3 for _ in range(N.bit_length())]
# 両方0
dp[-1][1] = 1
# 片方1
dp[-1][0] = 1
for i in reversed(range(N.bit_length() - 1)):
    if N >> i & 1:
        # 両方0
        # dp[i][(j << 1) + 1] += dp[i + 1][j]
        dp[i][1] += dp[i + 1][0]
        dp[i][2] += dp[i + 1][1]
        dp[i][2] += dp[i + 1][2]
        # 片方1
        # dp[i][j << 1] += dp[i + 1][j]
        dp[i][0] += dp[i + 1][0]
        dp[i][2] += dp[i + 1][1]
        dp[i][2] += dp[i + 1][2]
        # 両方1
        # dp[i][(j << 1) - 1] += dp[i + 1][j]
        dp[i][1] += dp[i + 1][1]
        dp[i][2] += dp[i + 1][2]
    else:
        # 両方0
        # dp[i][j << 1] += dp[i + 1][j]
        dp[i][0] += dp[i + 1][0]
        dp[i][2] += dp[i + 1][1]
        dp[i][2] += dp[i + 1][2]
        # 片方1
        # dp[i][(j << 1) - 1] += dp[i + 1][j]
        dp[i][1] += dp[i + 1][1]
        dp[i][2] += dp[i + 1][2]
        # 両方1
        # dp[i][(j << 1) - 2] += dp[i + 1][j]
        dp[i][0] += dp[i + 1][1]
        dp[i][2] += dp[i + 1][2]
    dp[i][0] %= MOD
    dp[i][1] %= MOD
    dp[i][2] %= MOD
print(sum(dp[0]) % MOD)

Submission status: Accepted

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

def func(N):
    S=str(bin(N))[2:]
    L=len(S)
    dp=[[0]*3 for i in range(L+1)]
    dp[0][0]=1
    for i in range(L):
        n=ord(S[i])-ord('0')
        for k in range(3):
            for s in range(3):
                if 2*s+n-k<0:
                    continue
                sd=min(2*s+n-k,2)
                dp[i+1][sd]+=dp[i][s]
                dp[i+1][sd]%=MOD
    return (dp[L][0]+dp[L][1]+dp[L][2])%MOD
print(func(N))

Submission status: Accepted

Solution code:
n = int(raw_input())
bn = bin(n)[2:]
dp = [[0]*3 for i in range(len(bn) + 1)]
mod = 10**9+7
dp[len(bn)][0] = 1
for d in range(len(bn)-1, -1, -1):
    if bn[len(bn)-1 - d] == "1":
        dp[d][0] = dp[d+1][0]
        dp[d][1] = dp[d+1][0] + dp[d+1][1]
        dp[d][2] = 2*dp[d+1][1] + 3*dp[d+1][2]
    else:
        dp[d][0] = dp[d+1][0] + dp[d+1][1]
        dp[d][1] = dp[d+1][1]
        dp[d][2] = dp[d+1][1] + 3*dp[d+1][2]
print (dp[0][0] + dp[0][1] + dp[0][2]) % mod

Submission status: Accepted

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

M = len(bin(N)) - 2
dp = [[0] * 3 for _ in range(M + 1)]
dp[0][0] = 1

for i in range(M) :
    if N >> (M - i - 1) & 1 :
        dp[i + 1][0] = dp[i][0] % MOD
        dp[i + 1][1] = (dp[i][0] + dp[i][1]) % MOD
        dp[i + 1][2] = (dp[i][1] * 2 + dp[i][2] * 3) % MOD
    else :
        dp[i + 1][0] = (dp[i][0] + dp[i][1]) % MOD
        dp[i + 1][1] = dp[i][1] % MOD
        dp[i + 1][2] = (dp[i][1] + dp[i][2] * 3) % MOD
        
print(sum(dp[-1]) % MOD)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
d=n.bit_length()
DP=[[0]*3 for _ in range(d+1)]
DP[0][0]=1
for i in range(d):
    if n>>(d-i-1)&1:
        DP[i+1][0]=DP[i][0]
        DP[i+1][1]=(DP[i][0]+DP[i][1])%mod
        DP[i+1][2]=(DP[i][1]*2+DP[i][2]*3)%mod
    else:
        DP[i+1][0]=(DP[i][0]+DP[i][1])%mod
        DP[i+1][1]=DP[i][1]
        DP[i+1][2]=(DP[i][1]+DP[i][2]*3)%mod
print(sum(DP[-1])%mod)

Submission status: Accepted

Solution code:
from functools import lru_cache

MOD = 10**9 + 7

@lru_cache(None)
def F(N):
  # (u,v) = (a^b,a+b), (a^b,a+b+1) という組の個数x,y. where v <= N
  if N == 0:
    return 1,1
  x,y = 0,0
  # (0,0) mod 2
  x1,y1 = F(N//2)
  x += x1
  y += x1
  # (0,1) mod 2
  x2,y2 = F((N-1)//2)
  x += x2
  y += y2
  # (1,1) mod 2
  if N > 1:
    x3,y3 = F((N-2)//2)
    x += y3
    y += y3

  return x%MOD,y%MOD
  
answer = F(int(input()))[0]
           
print(answer)

Submission status: Accepted

Solution code:

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 = [[0]*(3) for _ in range(len(N) + 1)]
    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] += 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(mymod((dp[0][0] + dp[0][1] + dp[0][2])))


if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
def xor_sum(N: int)->int:
    MOD = 10**9 + 7

    digits = len(bin(N)) - 2

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

    for i in range(digits):
        if N >> (digits - 1 - i) & 1:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = (dp[i][0] + dp[i][1]) % MOD
            dp[i+1][2] = (dp[i][1] * 2 + dp[i][2] * 3) % MOD
        else:
            dp[i+1][0] = (dp[i][0] + dp[i][1]) % MOD
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = (dp[i][1] + dp[i][2] * 3) % MOD

    return sum(dp[digits]) % MOD


if __name__ == "__main__":
    N = int(input())
    ans = xor_sum(N)
    print(ans)

Submission status: Accepted

Solution code:
P=10**9+7
inv2=(1+P)//2
def exp(a,k):
    if k==0:
        return 1
    elif k%2==0:
        return (exp(a*a,k//2))%P
    else:
        return (a*exp(a*a,k//2))%P
D=dict()
def f(N):
    if N in D:
        return D[N]
    if N<=1:
        D[N]=N
        return N
    i=0
    while(1):
        if 2**i<=N<2**(i+1):
            break
        i+=1
    if N==2**i:
        D[N]=((1+exp(3,i))*inv2)%P
        return D[N]
    D[N]=(f(N-2**i)-f(2**(i+1)-N-1)+exp(3,i))%P
    return D[N]
print(f(int(input())+1))

Submission status: Accepted

Solution code:
n = int(input())

MOD = 10 ** 9 + 7

k = len(bin(n)) - 2

dp = [[0, 0, 0] for _ in range(k + 1)]

dp[0][0] = 1

for i in range(k):
    if (n >> (k - 1 - i)) & 1:
        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
    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] + dp[i][2] * 3
    map(lambda x:x%MOD, dp[k])

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

Submission status: Accepted

Solution code:
n = int(input())
d = len(bin(n)) - 2
mod = 10**9 + 7
dp = [[0 for j in range(3)] for i in range(d+1)]
dp[d][0] = 1
for i in range(d):
    k = d - 1 - i
    for j in range(3):
        if j == 0:
            if (n >> k) & 1:
                dp[k][0] += dp[k+1][0]
                dp[k][1] += dp[k+1][0]
            else:
                dp[k][0] += dp[k+1][0]
        elif j == 1:
            if (n >> k) & 1:
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1] * 2
            else:
                dp[k][0] += dp[k+1][1]
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1]
        else:
            dp[k][2] += dp[k+1][2] * 3
        map(lambda x:x%mod, dp[k])
print(sum(dp[0]) % mod)

Submission status: Accepted

Solution code:
n=int(input())
nstr=bin(n)[2:]
thrpow=[1]
now=1
for k in range(len(nstr)):
    now=(now*3)%(10**9+7)
    thrpow.append(now)
f=dict()
g=dict()
if nstr[-1]=='0':f[1]=1
elif nstr[-1]=='1':f[1]=2
g[1]=3
for k in range(2,len(nstr)+1):
    if nstr[-k]=='0':
        f[k]=(f[k-1])%(10**9+7)
        g[k]=(thrpow[k-1]+f[k-1]+g[k-1])%(10**9+7)
    if nstr[-k]=='1':
        f[k]=(f[k-1]+g[k-1])%(10**9+7)
        g[k]=(2*thrpow[k-1]+g[k-1])%(10**9+7)
print(f[len(nstr)])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

N=int(input())
mod=10**9+7
DP=dict()
DP[(0,0)]=1#a+b,a^b
DP[(1,0)]=1
DP[(1,1)]=2

def ans(S,X):
    #print(S,X)
    if DP.get((S,X))!=None:
        return DP[(S,X)]
    if S==0:
        return 1
    #if X>S:
    #    return ans(S,S)
    

    DP[(S,X)]=(ans(S//2,X//2)+ans((S-1)//2,(X-1)//2)+ans((S-2)//2,(X-2)//2))%mod
    #一番下の桁をみて、bitが0,0の場合,1,0の場合,1,1の場合.
    #三つ目の場合は本来ans((S-2)//2,X//2)だが,今回扱うのはS=Xのときで,X>Sのときは0になるので,ans((S-2)//2,(X-2)//2)で良いはず.
    return DP[(S,X)]

print(ans(N,N))

Submission status: Accepted

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

ANSLIST=[1]
for i in range(61):
    ANSLIST.append((ANSLIST[-1]*3-1)%mod)

ANS=[1, 2, 4, 5]
ANSDICT=dict()
def ans(k):
    if 0<=k<=3:
        return ANS[k]
    if ANSDICT.get(k)!=None:
        return ANSDICT[k]
    for i in range(61):
        if k==2**i-2:
            return ANSLIST[i]-1
        if k==2**i-1:
            return ANSLIST[i]
        if 2**i-1>k:
            break
    x=k-(2**(i-1)-1)

    ANSDICT[k]=(ans(x-1)+ANSLIST[i-1]*2-ans(2**(i-1)-x-2)-1)%mod
    return ANSDICT[k]

print(ans(N))