解题思路

题意概括： 小 A 从原点 $(0,0)$ 出发，在无限大的平面直角坐标系中，每一步只能走 上、左、右 三个方向之一，步长为 1。要求走的过程中 不能到达已经到过的点。给定步数 $n$，求走恰好 $n$ 步的合法方案数，结果对 $10^9+7$ 取模。 样例：$n=2$ 时共有 7 种，题面已给出。

1. 关键性质分析

1. 没有“下”这个方向，所以纵坐标 $y$ 永远不降低，只会保持或增加。 因此每一条路径的纵坐标序列是单调不减的。

2. 由于不能走到重复的点：

   • 在同一行（相同的 $y$）内，只能一直向同一水平方向走，不能来回折返，否则会回到旧点。
   • 同一行上的点是按顺序依次走出来的一个连续线段，不能“跳格”。

3. 非常关键的一点：

   • 如果最后一步是向上走（记为 V）： 我们从某个点 $(x,y)$ 走到 $(x,y+1)$。因为还从未到达过第 $y+1$ 行，所以：

     • 上方 $(x,y+2)$ 没走过；
     • 左上 $(x-1,y+1)$、右上 $(x+1,y+1)$ 也没走过。 因此下一步可以走的合法方向 恰好有 3 种（上、左、右）。

   • 如果最后一步是水平走（记为 H）： 假设从 $(x,y)$ 水平走到 $(x+1,y)$，此时：

     • 回头走回 $(x,y)$ 不行（已经走过）；
     • 继续向前水平走到 $(x+2,y)$ 是新的点，可以；
     • 向上走到 $(x+1,y+1)$ 行也尚未出现，可以。 因为不能从上方再回到这一行，所以这一行的点只会从左到右（或从右到左）被依次走出来，不会有“提前造好的点”。 所以下一步可走的合法方向 恰好有 2 种（前进 或 上）。

   结论：扩展一条合法路径时，能走的下一步数量只与“上一走法是竖直还是水平”有关，与更早的历史无关。 这使得我们可以用一个简单的状态 DP 来抽象整个过程。

2. 状态设计与递推

设：

• $V_n$：长度为 $n$，且 最后一步是向上 的路径数；
• $H_n$：长度为 $n$，且 最后一步是水平 的路径数；
• $f_n = V_n + H_n$：长度为 $n$ 的所有合法路径数（答案）。

2.1 初始值

$n=1$ 时，从原点出发：

• 向上：$(0,0)\rightarrow(0,1)$，共 1 条 → $V_1=1$
• 向左 / 向右：共 2 条 → $H_1=2$

因此 $f_1 = 3$。 为了递推方便，再约定 $f_0 = 1$（走 0 步只有 1 种“空路径”）。

2.2 转移关系

根据上面的几何分析：

1. 要得到长度为 $n$ 且最后一步是 向上 的路径：

   • 只需在任意一条长度为 $n-1$ 的合法路径后面，加一个“向上”即可。 因为上一行还未到达过，不会撞点。

   • 所以

     $$V_n = f_{n-1} = V_{n-1} + H_{n-1}$$

2. 要得到长度为 $n$ 且最后一步是 水平 的路径：

   • 如果第 $n-1$ 步是向上（V），那么第 $n$ 步水平可以往左或往右，一共 2 种扩展： $\Rightarrow 2 \cdot V_{n-1}$

   • 如果第 $n-1$ 步是水平（H），那第 $n$ 步只能继续朝同一水平方向走（不能回头），只有 1 种扩展： $\Rightarrow 1 \cdot H_{n-1}$

   • 因此

     $$H_n = 2V_{n-1} + H_{n-1}$$

3. 把 $V_n$ 用 $f$ 表示：

   • 我们有 $V_n = f_{n-1}$，且对 $n=1$ 成立（$V_1=1,f_0=1$）。

   • 若 $V_k = f_{k-1}$，则

     $$V_{k+1} = V_k + H_k = f_k$$

     于是归纳得到对所有 $n\ge1$ 都成立。

4. 再看 $H_n$：

   $$H_n = 2V_{n-1} + H_{n-1} = 2f_{n-2} + (f_{n-1} - V_{n-1}) = 2f_{n-2} + (f_{n-1}-f_{n-2}) = f_{n-1} + f_{n-2} $$

5. 最后总数：

   $$f_n = V_n + H_n = f_{n-1} + (f_{n-1}+f_{n-2}) = 2f_{n-1} + f_{n-2} $$

得到一个简单的二阶线性递推：

• $f_0 = 1$
• $f_1 = 3$
• $f_n = 2f_{n-1} + f_{n-2}$（$n\ge2$），结果都在模 $10^9+7$ 下计算。

用这个递推算出前几项： $1, 3, 7, 17, 41, 99, \dots$，与搜索打表完全一致。

3. 大数据范围与矩阵快速幂

题目给出 $1 \le n \le 10^9$，若直接从 1 推到 $n$ 需要 $O(n)$ 时间，会超时。

注意递推是二阶线性齐次的，我们可以用 矩阵快速幂 将时间降到 $O(\log n)$。

写成矩阵形式：

$$\begin{bmatrix} f_n \\ f_{n-1} \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} f_{n-1} \\ f_{n-2} \end{bmatrix} $$

记

$$M = \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}$$

则有：

$$\begin{bmatrix} f_n \\ f_{n-1} \end{bmatrix} = M^{\,n-1} \begin{bmatrix} f_1 \\ f_0 \end{bmatrix} = M^{\,n-1} \begin{bmatrix} 3 \\ 1 \end{bmatrix} $$

使用快速幂在模 $10^9+7$ 下计算 $M^{n-1}$，即可得到 $f_n$。

复杂度分析

矩阵是 $2\times 2$ 的，每一次矩阵乘法是常数次运算。

• 时间复杂度：$O(\log n)$
• 空间复杂度：$O(1)$

满足 $n$ 最多 $10^9$ 的要求。

代码实现

Python

import sys

MOD = 1000000007


# 计算答案的函数
def solve(n: int) -> int:
    # 特判小数据
    if n == 1:
        return 3

    # 递推矩阵 M = [[2, 1], [1, 0]]
    base = [[2, 1],
            [1, 0]]

    # 2x2 矩阵乘法（取模）
    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 mat_pow(p):
        # 单位矩阵
        res = [[1, 0],
               [0, 1]]
        m = [base[0][:], base[1][:]]
        while p > 0:
            if p & 1:
                res = mul(res, m)
            m = mul(m, m)
            p >>= 1
        return res

    mat = mat_pow(n - 1)

    f1, f0 = 3, 1  # f1 = f(1), f0 = f(0)
    # 乘以向量得到 f(n)
    fn = (mat[0][0] * f1 + mat[0][1] * f0) % MOD
    return fn


def main():
    data = sys.stdin.read().strip()
    if not data:
        return
    n = int(data)
    ans = solve(n)
    print(ans)


if __name__ == "__main__":
    main()

Java

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007L;

    // 计算 n 步的方案数
    static long solve(long n) {
        if (n == 1) return 3L;

        long[][] base = {
                {2L, 1L},
                {1L, 0L}
        };

        // 2x2 矩阵乘法（取模）
        long[][] mul(long[][] a, long[][] b) {
            long[][] c = new long[2][2];
            c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
            c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
            c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
            c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;
            return c;
        }

        // 矩阵快速幂
        long[][] matPow(long p) {
            long[][] res = {
                    {1L, 0L},
                    {0L, 1L}
            };
            long[][] m = {
                    {base[0][0], base[0][1]},
                    {base[1][0], base[1][1]}
            };
            while (p > 0) {
                if ((p & 1L) != 0) {
                    res = mul(res, m);
                }
                m = mul(m, m);
                p >>= 1;
            }
            return res;
        }

        long[][] mat = matPow(n - 1);
        long f1 = 3L, f0 = 1L;
        long fn = (mat[0][0] * f1 + mat[0][1] * f0) % MOD;
        return fn;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        if (!in.hasNextLong()) return;
        long n = in.nextLong();
        long ans = solve(n);
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

// 计算 n 步的方案数
long long solve(long long n) {
    if (n == 1) return 3LL;

    // 递推矩阵
    long long base[2][2] = {{2, 1},
                            {1, 0}};

    // 2x2 矩阵乘法（取模）
    auto mul = [](long long a[2][2], long long b[2][2], long long c[2][2]) {
        c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
        c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
        c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
        c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;
    };

    // 矩阵快速幂
    long long res[2][2] = {{1, 0},
                           {0, 1}}; // 单位矩阵
    long long m[2][2] = {{base[0][0], base[0][1]},
                         {base[1][0], base[1][1]}};
    long long tmp[2][2];

    long long p = n - 1;
    while (p > 0) {
        if (p & 1LL) {
            mul(res, m, tmp);
            // 把 tmp 拷贝回 res
            res[0][0] = tmp[0][0]; res[0][1] = tmp[0][1];
            res[1][0] = tmp[1][0]; res[1][1] = tmp[1][1];
        }
        mul(m, m, tmp);
        m[0][0] = tmp[0][0]; m[0][1] = tmp[0][1];
        m[1][0] = tmp[1][0]; m[1][1] = tmp[1][1];
        p >>= 1;
    }

    long long f1 = 3, f0 = 1;
    long long fn = (res[0][0] * f1 + res[0][1] * f0) % MOD;
    return fn;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    if (!(cin >> n)) return 0;
    cout << solve(n) << '\n';
    return 0;
}

题目内容

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

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

输入描述

输入只有一行，包含1个整数$n$（1≤n≤1000000000）

输出描述

输出$1$个整数，代表题目所有答案，如果答案过大，请将其对$10^9+7$取模。

注：$10^9+7$即1000000007，即模即求余运算

样例1

输入

2

输出

7

说明

从($0,0$)出发走$2$步，共$7$种合法走法:

$(0,0)->(0,1)->(0,2)$

$(0,0)->(0,1)->(1,1)$

$(0,0)->(0,1)->(-1,1)$

$(0,0)->(1,0)->(2,0)$

$(0,0)->(1,0)->(1,1)$

$(0,0)->(-1,0)->(-2,0)$

$(0,0)->(-1,0)->(-1,1)$