京东2025.08.02笔试第二题

题面

网传回忆版

一个机器人从无限大网格的 (0, 0) 点出发，每次只能向上、向左、向右移动一格，且走过的格子不能重复。求机器人恰好走 n 步的路径方案数是多少，结果对 10^9+7 取模。

样例输入

2

样例输出

7

分析

容易计算出f[0] = 1, f[1] = 3, f[2] = 7。注意到如果某条路径上一次左右移动，那么由它只能贡献2条新路径；而其他路径可以贡献3条新路径。

如何求出上一次左右移动的路径呢？我们追溯到再上一次的所有路径，这些路径的所有分支中，有且仅有一个分支向上走一格，而这个分支在之后将贡献3条新路径（即额外贡献一条路径）。

因此我们得到递推公式f[n] = f[n-1] * 2 + f[n-2]。

由于题目给的N比较大，还需要用矩阵快速幂进行加速，构造矩阵转移方程：

$$\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix}$$

代码

#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
typedef pair<int,int> pii;
//std::mt19937_64 rng(std::random_device{}());
const int mod = 1e9 + 7;
const int N = 1005, M = 1e5 + 5;
struct Matrix {
    int n, m;
    vector<vector<i64>> g;
    Matrix(int n, int m) {
        this->n = n;
        this->m = m;
        g.resize(n, vector<i64>(m, 0));
    }
    static Matrix new_E(int n) {
        auto res = Matrix(n, n);
        for (int i = 0; i < n; ++i) {
            res.g[i][i] = 1;
        }
        return res;
    }
    friend Matrix operator *(const Matrix &lhs, const Matrix &rhs) {
        assert(lhs.m == rhs.n);
        Matrix res = Matrix(lhs.n, rhs.m);
        for (int i = 0; i < lhs.n; ++i) {
            for (int j = 0; j < rhs.m; ++j) {
                for (int k = 0; k < lhs.m; ++k) {
                    res.g[i][j] = (res.g[i][j] + lhs.g[i][k] * rhs.g[k][j] % mod) % mod;
                }
            }
        }
        return res;
    }
    friend Matrix operator ^ (const Matrix &lhs, int k) {
        Matrix base = lhs;
        Matrix res = new_E(lhs.n);
        while (k) {
            if (k & 1) res = res * base;
            base = base * base;
            k >>= 1;
        }
        return res;
    }
};
void solve() {
    int n;
    cin >> n;
    vector<i64> f(100);
    f[0] = 1, f[1] = 3, f[2] = 7;
    Matrix b = Matrix(2, 1);
    b.g[0][0] = f[2];
    b.g[1][0] = f[1];
    Matrix x = Matrix(2, 2);
    x.g[0][0] = 2, x.g[0][1] = 1;
    x.g[1][0] = 1, x.g[1][1] = 0;
    for (int i = 3; i < 100; ++i) {
        b = x * b;
        f[i] = b.g[0][0];
        cout << "f[" << i << "]=" << f[i] << '\n';
    }
}
int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}