ACM3759 二维跑步题解

题目分析

这道题是二维空间上的随机游走。基本思路是：

观察转移规则，发现从任意 $y$ 出发，向右/原地/向左的选择数都是 $3,1,2$ ，与 $y$ 无关
由此直接写出总量的生成函数 $F_n(z) = (3z + 1 + 2z^{-1})^n$
转化为普通多项式后用三项递推 $O(n)$ 求出所有系数

最终复杂度 $O(n)$ 。

数学分析

设 $f_t(x)$ 为走 $t$ 步后落在 $x$ 处的总方案数（ $y$ 任意）。观察题目给出的转移规则：

当前位置	向右 $(x+1)$	原地 $(x)$	向左 $(x-1)$
$(i,0)$	到全部 3 个 $y$	保持 $y=0$	到 $y=1,2$ （2 种）
$(i,1)$	到全部 3 个 $y$	保持 $y=1$	到 $y=0,2$ （2 种）
$(i,2)$	到全部 3 个 $y$	保持 $y=2$	到 $y=0,1$ （2 种）

关键观察：无论当前在哪个 $y$ ，向右走都有 3 种选择，原地有 1 种，向左有 2 种。因此 $f_t$ 的递推与 $y$ 无关：

$f_{t+1}(x) = 3 f_t(x-1) + f_t(x) + 2 f_t(x+1)$

定义生成函数 $F_t(z) = \sum_{x \in \mathbb{Z}} f_t(x)\, z^x$ ，上式等价于：

$F_{t+1}(z) = (3z + 1 + 2z^{-1}) \cdot F_t(z)$

初始 $F_0(z) = 1$ （只有 $f_0(0)=1$ ），故：

$F_n(z) = (3z + 1 + 2z^{-1})^n$

问题转化为：求 $F_n(z)$ 中 $z^{-m}$ 到 $z^m$ 的系数之和。

化为普通多项式

$F_n(z) = (3z + 1 + 2z^{-1})^n = z^{-n} (3z^2 + z + 2)^n$

令 $Q(z) = 3z^2 + z + 2$ ， $Q(z)^n = \sum_{j=0}^{2n} c_j z^j$ 。则：

$F_n(z) = \sum_{j=0}^{2n} c_j\, z^{j-n}$

位置 $x = j-n$ 的方案数恰好是 $c_{x+n}$ 。答案即为：

$\text{ans} = \sum_{x=-m}^{m} c_{x+n} = \sum_{j = \max(0,\, n-m)}^{\min(2n,\, n+m)} c_j$

三项递推式

令 $P(z) = Q(z)^n$ 。对两边求导：

$P'(z) = n \cdot Q(z)^{n-1} \cdot Q'(z)$

两边同乘 $Q(z)$ ：

$P'(z) \cdot Q(z) = n \cdot P(z) \cdot Q'(z)$

将 $Q(z) = 3z^2 + z + 2$ ， $Q'(z) = 6z + 1$ ，以及 $Q(z)^n = \sum c_j z^j$ 代入，比较 $z^j$ 的系数：

$3(j-1)c_{j-1} + j c_j + 2(j+1)c_{j+1} = 6n c_{j-1} + n c_j$

整理得：

$2(j+1) c_{j+1} = (6n - 3j + 3) c_{j-1} + (n - j) c_j$

$\boxed{c_{j+1} = \frac{(6n - 3j + 3) \cdot c_{j-1} + (n - j) \cdot c_j}{2(j+1)}}$

初始条件

$c_0 = 2^n$ （所有因子都取常数项 $2$ ）
$c_{-1} = 0$ （多项式无负次项）
$j=0$ 时： $c_1 = \dfrac{n \cdot c_0}{2}$

由这三项递推式，可以 $O(n)$ 一次性算出全部 $c_0, c_1, \ldots, c_{2n}$ ，无需任何迭代 DP。

代码

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

int mod_pow(int base, int exp)
{
    int result = 1;
    while (exp) {
        if (exp & 1) result = (long long)result * base % MOD;
        base = (long long)base * base % MOD;
        exp >>= 1;
    }
    return result;
}

void precompute_inverses(int n, vector<int> &inv)
{
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (long long)(MOD - MOD / i) * inv[MOD % i] % MOD;
}

vector<int> compute_coefficients(int n, const vector<int> &inv)
{
    vector<int> c(2 * n + 1, 0);

    c[0] = mod_pow(2, n);

    if (n == 0) return c;

    c[1] = (long long)n * c[0] % MOD * inv[2] % MOD;

    for (int j = 1; j < 2 * n; ++j) {
        int term1 = (long long)(6LL * n - 3LL * j + 3) * c[j - 1] % MOD;
        int term2 = (long long)(n - j) * c[j] % MOD;
        int numerator = (term1 + term2) % MOD;
        if (numerator < 0) numerator += MOD;
        c[j + 1] = (long long)numerator * inv[2 * (j + 1)] % MOD;
    }

    return c;
}

int compute_answer(const vector<int> &c, int n, int m)
{
    int ans = 0;
    int lo = max(0, n - m);
    int hi = min(2 * n, n + m);
    for (int j = lo; j <= hi; ++j)
        ans = (ans + c[j]) % MOD;
    return ans;
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> inv(4 * n + 2);
    precompute_inverses(4 * n + 1, inv);

    vector<int> c = compute_coefficients(n, inv);
    cout << compute_answer(c, n, m) << endl;

    return 0;
}

复杂度分析

步骤	时间	空间
预处理逆元	$O(n)$	$O(n)$
递推求 $c_j$	$O(n)$	$O(n)$
区间求和	$O(\min(n, m))$	$O(1)$
总计	$O(n)$	$O(n)$

递推式每步只需两次乘法、一次加法、一次除法（乘逆元），常数极小
所需的模逆元 inv[1..4n] 可以 $O(n)$ 线性预处理
相比于迭代 DP 的 $O(n^2)$ ，此方法可以直接处理 $n$ 高达 $10^7$ 级别的数据

题解 | #二维跑步#

ACM3759 二维跑步 题解