「BJOI2017」机动训练 题解

问题转化 设地形序列 $s$ 在所有机动路径中出现 $cnt(s)$ 次，则：

每条地形序列为 $s$ 的路径权重为 $cnt(s)$

所有权重和 = $\sum_s cnt(s)^2$

这等价于统计地形序列相同的机动路径对的数量。

机动路径性质 “不远离终点” ⇒ 路径在 $x$ 和 $y$ 方向单调。 设终点相对于起点的方向为 $(dx,dy)$，其中 $dx,dy\in{-1,0,1}$ 且 $(dx,dy)\neq(0,0)$，则：

每步移动 $(p,q)$ 满足 $p\in{0,dx}, q\in{0,dy}, (p,q)\neq(0,0)$

因此路径单调且不自交

方向分类 共有 8 种 $(dx,dy)$ 组合，对应 8 个单调方向。 利用对称性，可归为 4 类：

水平/垂直（$dx·dy=0$）：4 个方向

对角线（$dx·dy\neq0$）：4 个方向

核心算法：双路径 DP 对每对方向 $(D_1,D_2)$（含同类和相反类），计算匹配路径对数。

定义 $f[x_1][y_1][x_2][y_2]$：第一条路径在 $(x_1,y_1)$（沿 $D_1$），第二条在 $(x_2,y_2)$（沿 $D_2$），且从起点到当前位置地形序列相同的方案数。

转移：对每个允许的移动 $(p_1,q_1)$（对 $D_1$）和 $(p_2,q_2)$（对 $D_2$）：

text 若 grid[x1+p1][y1+q1] = grid[x2+p2][y2+q2] 则 f[nx1][ny1][nx2][ny2] += f[x1][y1][x2][y2] 初始：$f[sx_1][sy_1][sx_2][sy_2]=1$，若两起点字符相同。

答案累计：当路径长度 ≥ 2（即已走步数 ≥ 1）时，累加到总答案。

时间复杂度 $O((mn)^2 × 9 × C)$，其中 $C≈16$（方向对常数），$m,n≤30$ 时可过。

最终答案 对所有方向对的结果乘对称系数求和，模 $10^9+9$。