跳转至

灵动坐标系

一觉醒来,小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} $$

快速幂

快速幂是计算机常用的一个小算法。

例如我们要计算$x^n$,如果n是偶数,就可以拆分为: $$ x^{n/2} \cdot x^{n/2} $$ 如此递归地进行下去就可以在$\mathcal{O}(\log n)$的时间复杂度下完成计算了。

或者更宏观地来看,我们对指数n做了如下分解(其实就是二进制转换): $$ n = d_02^0 + d_12^1 +\cdots $$ 其中$d_i \in \{0,1\}$。

从而 $$ x^n = (x^{2^0})^{d_0}\times (x^{2^1})^{d_1}\times \cdots $$ 代码实现如下:

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)

最后更新: 2025-08-03 03:17:56
创建日期: 2025-08-03 03:17:56

广告

人要恰饭的嘛🤑🤑

评论