灵动坐标系¶

一觉醒来，小A发现自己身处一个无限大的平面直角坐标系的原点。坐标系之神告诉他,他可以在这个坐标系内移动,但每一步只能选择上,左,右三个方向之一，并朝着这个方向移动1个单位的距离。特别的，坐标系之神要求小A不能经过相同的点。

坐标系之神告诉小A，只要他能算出走n步的合法方案数，就把他放回现实世界。小A刚醒来还无法深入思考，想你帮他计算一下结果。

问题规模：1 <= n <= 1e10，非常大！因此要求输出的答案对$10^9+7$取模。

题解¶

考虑递推公式。假设f(n)代表走n步的合法方案数。

那么f(n+1) = 2f(n) + f(n-1)。

这是因为n+1步的合法方案数可以分解为下面三种情况：

• 最后一步为上：倒数第二步任意
• 最后一步为左：倒数第二步上或者左
• 最后一步为右：倒数第二步上或者右

根据加法原理，得到：

f(n+1) = #{第n步任意} + #{第n步上或者左} + #{第n步上或者右}

合并一下得到：

f(n+1) = #{第n步任意} + #{第n步上或者左或者右} + #{第n步上}

而第n步为上 = 第n-1步任意的方案数，所以：

f(n+1) = 2 * #{第n步任意} + #{第n-1步任意}

也就是f(n+1) = 2f(n) + f(n-1)。

不难计算：f(1)=3, f(2)=7

递推¶

这是一个典型的线性递推数列，我们可以给出一个$\mathcal{O}(n)$的算法：

a,b = 3, 7
for _ in range(n-1):
    a,b = b,2*b+a
print(b)

但是这还不够快（起码jd这个笔试应该是要求更快的算法，否则ac不了）。

快速幂¶

实际上我们可以直接计算得到答案的通项： $$ f(n) = \frac{(1+\sqrt{2})^{n+1} + (1-\sqrt{2})^{n+1}}{2} $$

不难发现，n稍微大一些第二项就可以忽略不计，得到： $$ f(n) = \left\lceil \frac{(1+\sqrt{2})^{n+1}}{2} \right\rceil $$

但是这个东西是一个无理数幂次，想优化的话比较难，我还没查到怎么优化。

如果直接考虑递推公式的话，通常我们使用矩阵快速幂来优化： $$ \begin{bmatrix} f(n+1)\\f(n) \end{bmatrix}=\begin{bmatrix} 2&1\\ 1&0 \end{bmatrix}^{n-1}\begin{bmatrix} f(2)\\f(1) \end{bmatrix} $$

def quick_power(x, n):
    res = 1
    while n:
        # 如果最后一位是1，就乘上这个幂
        if n&1:
            res *= x
        x *= x
        n >>= 1
    return res

本题的代码如下：

MOD = 10**9 + 7

def mul(A,B):
    """矩阵乘法"""
    return [
        [
            (A[0][0]*B[0][0]+A[0][1]*B[1][0]) % MOD, 
            (A[0][0]*B[0][1]+A[0][1]*B[1][1]) % MOD
        ],
        [
            (A[1][0]*B[0][0]+A[1][1]*B[1][0]) % MOD, 
            (A[1][0]*B[0][1]+A[1][1]*B[1][1]) % MOD
        ],
    ]

def qpow(M, p):
    """矩阵快速幂"""
    R = [[1,0],[0,1]]
    while p:
        if p&1:
            R = mul(R,M)
        M = mul(M, M)
        p >>= 1
    return R

n = int(input())
A = qpow([[2,1],[1,0]], n-1)
res = (3*A[0][0] + A[0][1]) % MOD
print(res)