题目描述

在一个无限大的平面直角坐标系中，小A 从原点出发，每一步只能向“上”、“左”、“右”三个方向之一移动 1 个单位，且不允许经过相同的点。求小A 恰好走到第$n$ 步时的合法走法总数。由于结果可能很大，需对$10^9+7$ 取模输出。

完整思路

1. 状态定义

   • 令$a_n$表示恰好走$n$步的合法路径总数。
   • 令$b_n$表示恰好走$n$步，且第$n$步是水平移动（“左”或“右”）的路径数。

2. 分析 “第$n$步” 的贡献

   • 如果第$n$步向“上”移动，那么前$n-1$步可以是任意合法路径，共$a_{n-1}$ 种情况。
   • 如果第$n$步水平移动，本来有2个方向，但要排除“回到”第$n-1$步所在点的情况。若前一步也是水平移动，则会回头；这部分有$b_{n-1}$种，需要减去。

   因此 $b_n \;=\;2\,a_{n-1}\;-\;b_{n-1}.$

3. 连接$a_n$ 与 $b_n$

   第 $n$ 步总的选择数为“向上”＋“水平”，即 $a_n \;=\;a_{n-1}\;+\;b_n.$

4. 合并推导

   • 由$b_n$定义可得 $b_n + b_{n-1} = 2\,a_{n-1}.$
   • 又因为 $b_n = a_n - a_{n-1},\quad b_{n-1}=a_{n-1}-a_{n-2},$
   • 将它们带入上式： $(a_n - a_{n-1})+(a_{n-1}-a_{n-2}) = 2\,a_{n-1}$ $\;\;\Longrightarrow\;a_n - a_{n-2} = 2\,a_{n-1}$ $\;\;\Longrightarrow\;a_n = 2\,a_{n-1} + a_{n-2}.$

5. 初始边界 $a_0 = 1,\qquad a_1 = 3.$

6. 计算优化

   • 将递推写成矩阵形式：
   • 利用$2\times2$ 矩阵快速幂，时间复杂度降为$O(log n)$

7. 结果取模 全程对$10^9+7$ 取模，避免溢出。

C++

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;

// 矩阵乘法
vector<vector<long long>> mul(const vector<vector<long long>>& A,
                              const vector<vector<long long>>& B) {
    vector<vector<long long>> C(2, vector<long long>(2));
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

// 矩阵快速幂
vector<vector<long long>> mat_pow(vector<vector<long long>> M, long long p) {
    vector<vector<long long>> R = {{1,0},{0,1}}; // 单位矩阵
    while (p) {
        if (p & 1) R = mul(R, M);
        M = mul(M, M);
        p >>= 1;
    }
    return R;
}

long long count_paths(long long n) {
    if (n == 0) return 1;
    if (n == 1) return 3;
    // 变换矩阵
    vector<vector<long long>> M = {{2,1},{1,0}};
    // 计算 M^(n-1)
    vector<vector<long long>> P = mat_pow(M, n-1);
    // [a_n, a_{n-1}]^T = P * [a_1, a_0]^T = P * [3,1]^T
    return (P[0][0] * 3 + P[0][1] * 1) % MOD;
}

int main() {
    long long n;
    cin >> n;
    cout << count_paths(n) << "\n";
    return 0;
}

Python

MOD = 10**9 + 7

def mat_mul(A, B):
    # 返回 2x2 矩阵 A*B（模 MOD）
    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(M, p):
    # 矩阵快速幂
    R = [[1, 0], [0, 1]]  # 单位矩阵
    while p:
        if p & 1:
            R = mat_mul(R, M)
        M = mat_mul(M, M)
        p >>= 1
    return R

def count_paths(n):
    if n == 0:
        return 1
    if n == 1:
        return 3
    M = [[2, 1], [1, 0]]
    P = mat_pow(M, n-1)
    # [a_n, a_{n-1}] = P * [a_1, a_0] = P * [3,1]
    return (P[0][0] * 3 + P[0][1] * 1) % MOD

if __name__ == "__main__":
    n = int(input())
    print(count_paths(n))

Java

import java.util.Scanner;

public class Main {
    static final long MOD = 1000000007;

    // 矩阵乘法
    static long[][] mul(long[][] A, long[][] B) {
        long[][] C = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
                }
            }
        }
        return C;
    }

    // 矩阵快速幂
    static long[][] matPow(long[][] M, long p) {
        long[][] R = {{1, 0}, {0, 1}}; // 单位矩阵
        while (p > 0) {
            if ((p & 1) == 1) {
                R = mul(R, M);
            }
            M = mul(M, M);
            p >>= 1;
        }
        return R;
    }

    // 计算走 n 步的方案数
    static long countPaths(long n) {
        if (n == 0) return 1;
        if (n == 1) return 3;
        long[][] M = {{2, 1}, {1, 0}};
        long[][] P = matPow(M, n - 1);
        // [a_n, a_{n-1}] = P * [3,1]
        return (P[0][0] * 3 + P[0][1] * 1) % MOD;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        System.out.println(countPaths(n));
        sc.close();
    }
}

题目内容

一觉醒来，小$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)$