题解 | 循环汉诺塔

先自己在草稿纸上模拟了一下步骤，总结思路如下：

# 首先我们假设n个圆盘全部移动到B所需次数为L(n)，全部到C为R(n)

# 一、对于全部移动到B的

# 1.首先前(n - 1)个一堆移动到C，该步骤次数为R(n - 1)

# 2.将n移动到B，操作1次

# 3.将前(n - 1)个一堆移动到B，该步骤次数为R(n - 1)

# 总次数L(n) = 2 * R(n - 1) + 1

# 二、对于全部移动到C的

# 1.首先前(n - 1)个一堆移动到C，该步骤次数为R(n - 1)

# 2.将n移动到B，操作1次

# 3.将前(n - 1)个一堆移动到A，该步骤次数为L(n - 1)

# 4.将n移动到C，操作1次

# 3.将前(n - 1)个一堆移动到C，该步骤次数为R(n - 1)

# 总次数R(n) = 2 * R(n - 1) + L(n - 1) + 2

于是，直接写出：

def L(n):
    if n == 1:
        return 1
    else:
        return 2 * R(n - 1) + 1

def R(n):
    if n == 1:
        return 2
    else:
        return 2 * R(n - 1) + L(n - 1) + 2
    
MOD = 10**9 + 7
def solve():
    n = int(input())
    print(L(n) % MOD, R(n) % MOD)
solve()

函数互相调用，时间复杂度O(2^n)，这简直是左脚踩右脚想上天？

稍微修改一下：

MOD = 10**9 + 7
def solve():
    n = int(input())
    if n == 1:
        print(1, 2)
        return

    L_prev, R_prev = 1, 2
    for i in range(2, n + 1):
        L_curr = (2 * R_prev + 1) % MOD
        R_curr = (2 * R_prev + L_prev + 2) % MOD
        L_prev, R_prev = L_curr, R_curr
    print(L_prev, R_prev)
solve()

心想简直so eazy时间复杂度O(n)还过不了？

结果还真过不了...

转头用矩阵，快速进行幂计算：

MOD = 10**9 + 7
def matrix_mutl(A, B):
    return [
        [
            (A[0][0] * B[0][0] + A[0][1] * B[1][0] + A[0][2] * B[2][0]) % MOD,
            (A[0][0] * B[0][1] + A[0][1] * B[1][1] + A[0][2] * B[2][1]) % MOD,
            (A[0][0] * B[0][2] + A[0][1] * B[1][2] + A[0][2] * B[2][2]) % MOD,
        ],
        [
            (A[1][0] * B[0][0] + A[1][1] * B[1][0] + A[1][2] * B[2][0]) % MOD,
            (A[1][0] * B[0][1] + A[1][1] * B[1][1] + A[1][2] * B[2][1]) % MOD,
            (A[1][0] * B[0][2] + A[1][1] * B[1][2] + A[1][2] * B[2][2]) % MOD,
        ],
        [
            (A[2][0] * B[0][0] + A[2][1] * B[1][0] + A[2][2] * B[2][0]) % MOD,
            (A[2][0] * B[0][1] + A[2][1] * B[1][1] + A[2][2] * B[2][1]) % MOD,
            (A[2][0] * B[0][2] + A[2][1] * B[1][2] + A[2][2] * B[2][2]) % MOD,
        ],
    ]

def matrix_pow(mat, power):
    res = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    while power > 0:
        if power % 2 == 1:
            res = matrix_mutl(res, mat)
        mat = matrix_mutl(mat, mat)
        power //= 2
    return res

def solve():
    n = int(input())
    if n == 1:
        print(1, 2)
    else:
        M = [[0, 2, 1], [1, 2, 2], [0, 0, 1]]
        X_1 = [1, 2, 1]
        M_power = matrix_pow(M, n - 1)
        L_n = (M_power[0][0] * X_1[0] + M_power[0][1] * X_1[1] + M_power[0][2] * X_1[2]) % MOD
        R_n = (M_power[1][0] * X_1[0] + M_power[1][1] * X_1[1] + M_power[1][2] * X_1[2]) % MOD
        print(L_n, R_n)
solve()

不容易真不容易...