题解 | 小红蹦跳蹦跳

fmin = lambda x, y: x if x < y else y
fmax = lambda x, y: x if x > y else y

mod = 10 ** 9 + 7

# @TIME
def solve(testcase):
    n = II()

    if n == 1:
        print(1)
        return

    dpl = [0 for _ in range(n + 1)]
    dpr = [0 for _ in range(n + 1)]
    dpl[0] = 1
    dpr[0] = 1

    pslo = [0 for _ in range(n + 1)]
    psro = [0 for _ in range(n + 1)]
    psle = [0 for _ in range(n + 1)]
    psre = [0 for _ in range(n + 1)]
    psle[0] = 1
    psre[0] = 1

    for i in range(1, n + 1):
        if i & 1:
            dpl[i] = psre[i - 1]
            pslo[i] = dpl[i]
            dpr[i] = pslo[i - 2]
            psro[i] = dpr[i]
        else:
            dpl[i] = psro[i - 1]
            psle[i] = dpl[i]
            dpr[i] = psle[i - 2]
            psre[i] = dpr[i]
        
        pslo[i] = (pslo[i] + pslo[i - 1]) % mod
        psle[i] = (psle[i] + psle[i - 1]) % mod
        psro[i] = (psro[i] + psro[i - 1]) % mod
        psre[i] = (psre[i] + psre[i - 1]) % mod
    
    print((dpl[n] + dpr[n]) % mod)

for testcase in range(1):
    solve(testcase)