zero_2.py

from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)

@lru_cache(maxsize=10**6)
def f(n,m):
    #print(n,m)
    if n==0:
        if m==0:
            return (0,0,0)
        else:
            return (0,1,0)
        
    L_n=5*2**n-4
    L_n_1=5*2**(n-1)-4
    if m==L_n:
        return (2**(n+1)-2,2**n,2**(n+1)-2)
    elif m>L_n:
        return f(m,L_n)
    elif m<L_n:
        if 0<=m<1:
            return (0,0,0)
        elif 1<=m<2:
            #[
            return (1,0,0)
        elif 2<=m<L_n_1+2:
            #[f(n-1,m-1)
            a,b,c=f(n-1,m-1)
            return (1+a,b,c)
        elif L_n_1+2<=m<L_n_1+3:
            #[f(n-1,L_{n-1)]
            a,b,c=f(n-1,m-2)
            return (a+1,b,c+1)
        elif L_n_1+3<=m<L_n_1+4:
            #[f(n-1),L_{n-1}][
            a,b,c=f(n,m-1)
            return (a+1,b,c)
        elif L_n_1+4<=m<L_n_1+4+L_n_1:
            #[f(n-1),L_{n-1}][f(n-1,m-L_{n-1}-3)
            a,b,c=f(n-1,m-L_n_1-3)
            x,y,z=f(n,L_n_1+3)
            return (a+x,b+y,c+z)
n=30000
m=10**18
print(f(n,m))

#(400000000000017993, 199999999999994012, 399999999999987995)