Share my thinking and impove the method


  • 1
    H

    first come up solution:

     f: rewardable
     LL: f end with LL
     L: f end with L
     A: f contain with A
     ALL: f contain with A and end with LL
     AL: f contain with A and end with L
    
     f[i] = f[i-1] + f[i-1]-LL[i-1]+f[i-1]-A[i-1] # end with P, L, A
     A[i] = A[i-1] + A[i-1]-ALL[i-1]+f[i-1]-A[i-1] # end with P, L, A
     LL[i] = L[i-1] - LL[i-1] # end with L
     L[i] = f[i-1] - LL[i-1] # end with L
     ALL[i] = AL[i-1] - ALL[i-1] # end with L
     AL[i] = A[i-1] - ALL[i-1] # end with L
    

    get TLE, but i didn't realize that can solve by exp. of square, i try to reduce the parameter.
    and get LL[i] = f[i-2] - LL[i-2] - LL[i-1], ALL[i] = A[i-2] - ALL[i-2] - ALL[i-1] and the f & A function, remove the AL and L, still get TLE. I decided continue do, get f[i] = (f[i-1]*3 - f[i-4]*2 + A[i-4] - A[i-1]), A[i] = (A[i-1]-f[i-4]+f[i-1]), doesn't work. finally i remove the function A, get the pure f funcionf[i] = f[i-1]*3-f[i-2]-f[i-3]-f[i-4]*3+f[i-5]+f[i-6]+f[i-7], finally pass. but it's O(n) time.

    f = [1, 3, 8, 19, 43, 94, 200, 418]
    if n < 8:
        return f[n]
    for _ in range(7, n):
        f[:7] = f[1:]
        f[7] = (3*f[6]-f[5]-f[4]-3*f[3]+f[2]+f[1]+f[0]) % 1000000007
    return f[7]
    

    In fact, every time, we just calculate the map.
    0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 0 1 0 0 0
    0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0
    0 0 0 0 0 0 0 1
    0 1 1 1 -3 -1 -1 3
    used exponentiating by squaring , the time is O(log(n))

    def matrix_multi(a, b):
        m, s, n = len(a), len(a[0]), len(b[0])
        if len(b) != s:
            return
        rmtr = [[0]*m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                rmtr[i][j] = sum(a[i][k]*b[k][j] for k in range(s)) % 1000000007
        return rmtr
                    
    f = [1, 3, 8, 19, 43, 94, 200, 418]
    if n < 8:
        return f[n]
    t = n-7
    p = [[0]*8 for _ in range(8)]
    for i in range(8):
        p[i][i] = 1
    mtx = [[0]*8 for _ in range(8)]
    for i in range(7):
        mtx[i][i+1] = 1
    mtx[7] = [0, 1, 1, 1, -3, -1, -1, 3]
    while t:
        if t & 1:
            p = matrix_multi(p, mtx)
        mtx = matrix_multi(mtx, mtx)
        t >>= 1
    return sum(x*y for x,y in zip(p[7], f)) % 1000000007
    

    Actually, i should used in the begining.
    [f[i], A[i], LL[i], L[i], ALL[i], AL[i]] = map([f[i-1], A[i-1], LL[i-1], L[i-1], ALL[i-1], AL[i-1]]

    def matrix_multi(a, b):
        m, s, n = len(a), len(a[0]), len(b[0])
        if len(b) != s:
            return
        rmtr = [[0]*m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                rmtr[i][j] = sum(a[i][k]*b[k][j] for k in range(s)) % 1000000007
        return rmtr
    
    p = [[0]*6 for _ in range(6)]
    for i in range(6):
        p[i][i] = 1
    mtx = [\
    [3, -1, -1, 0, 0, 0],
    [1, 1, 0, 0, -1, 0],
    [0, 0, -1, 1, 0, 0],
    [1, 0 , -1, 0, 0, 0],
    [0, 0, 0, 0, -1, 1], 
    [0, 1, 0, 0, -1, 0]]
    while n:
        if n & 1:
            p = matrix_multi(p, mtx)
        mtx = matrix_multi(mtx, mtx)
        n >>= 1
    return p[0][0]
    

    other matrix also can be generated by the A | L, like the top votes solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.