关于 K 维空间中整点之间曼哈顿距离最短路径计数问题

标签：MD right 维空间 整点 路径 AMDC 计数问题 left

约定

\(K\) 维空间中，整点的坐标以 \(K\) 个整数表示，形如

\[Point\left(X_1,X_2,\cdots,X_k\right) \]

定义两个点的曼哈顿距离为 每一维坐标差的绝对值之和，记为

\[MD\left(A, B\right) = \sum_{i=1}^{K} \left|{X_{i_A}-X_{i_B}}\right| \]

定义两个点 \(A\) , \(B\) 相邻 当且仅当满足

\[MD\left(A, B\right) = 1 \]

最短路径计数

每次只能移动到相邻的点，容易发现 \(S\) 到 \(T\) 的曼哈顿距离最短路径可能经过的点构成了一个 \(K\) 维方体，而 \(S\) 和 \(T\) 正为此方体相对的两个顶点。

三维空间中示意图如下：

我们定义在第 \(i\) 维坐标上 \(\pm 1\) 为操作 \(i\)，显然的是，需要什么操作及具体个数是已知的，总数为

\[MD\left(S,T\right) \]

那么一条路径就可以转换成一个操作序列，不同的路径数量等价于本质不同的序列数量。
两个序列本质不同当且仅当至少存在一个位置上的操作编号不同。

显然在排列中，同样的操作本质不同，但实际上，它们是相同的，所以需要去重。

则总方案数为

\[\frac{MD\left(S,T\right)!}{\Pi_{i=1}^{K} \left(\left|{X_{i_S}-X_{i_T}}\right|!\right)} \]

扩展

假定在此 \(K\) 维空间中，存在一些整点是不能经过的（保证不为 \(S\) 和 \(T\)），那么 \(S\) 到 \(T\) 的最短路径数量会有什么变化呢？

我们称不能经过的点为 标记点
并定义两个点之间不经过标记点的最短路径条数为

\[AMDC\left(A,B\right) \]

在不考虑标记点时，

\[AMCD\left(A, B\right) = \frac{MD\left(A,B\right)!}{\Pi_{i=1}^{K} \left(\left|{X_{i_A}-X_{i_B}}\right|!\right)} \]

同时令

\[f_i=AMDC\left(S,i\right) \]

显然，真正对我们有用的只有 \(K\) 维方体内的标记点和 \(T\) 点的 \(f\) 值，考虑 \(DP\) 转移。

那么，\(A\) 点对 \(B\) 点的 \(f\) 造成影响的充要条件是什么？
可以发现为

\[x_{i_A} \le x_{i_B} \left( x | x \in \left[ 1,K \right] \right) \]

也就是 \(K\) 维偏序。

所以

\[f_i = AMDC\left( S, i \right) - \sum_{j} g\left(j, i\right) \times f_j \times AMDC\left(j, i\right) \]

其中，

\[g\left(A, B\right) = \left\{ \begin{aligned} 1 \qquad& x_{i_A} \le x_{i_B} \left( x | x \in \left[ 1,K \right] \right)\\ 0 \qquad& other \end{aligned}\right. \]

满足 \(g\left(S, T\right) = 1\)

用到了一点小容斥。
可以画一下二维空间中的图来帮助理解。

如有任何问题请私信作者 @qkhm

标签：MD,right,维空间,整点,路径,AMDC,计数问题,left
From： https://www.cnblogs.com/qkhm/p/17770240.html