「JSOI2018」机器人(“Jsoi2018” robot)

在本题当中为了方便,我们将坐标范围改至 \((0 \sim n – 1, 0 \sim m – 1)\),行走即可视作任意一维在模意义下 \(+1\).

同时,注意到一个位置只能经过一次,则可以令 \(a_{x, y}\) 为 \((x, y)\) 这个位置往外走是向下还是向,方便考察。

首先考虑这个问题的方案数,此类网格图行走的问题一般需要考察对角线的特殊性质。

  • 观察 1:\(\forall (x, y)\),若 \(a_{(x – 1) \bmod n, y} \ne a_{x, (y – 1) \bmod m}\),则要么 \((x, y)\) 被经过了两次,要么没有被经过。
  • 推论 1:\(\forall a, x, y, a_{x, y} = a_{(x + a) \bmod n, (y – a) \bmod m}\)

考察推论 1 的组合表示,相当于将整个网格图分为了若干个组,每个组由若干条完整的副对角线构成,每组内 \(a\) 相同,很自然地我们可以进一步考虑每个组对角线的构成。

将网格图往左右不断复制延伸,考察一下此时 \((0, 0)\) 所在组内副对角线的在第一行的开头位置构成的集合。

不难发现即为 \(nx(x \in \mathbb{N})\),对应到原网格图内就是 \(nx \bmod m(x \in \mathbb{N})\) 的值。

根据裴蜀定理,这个值一定是 \(dx(d = (n, m), 0 \le x < \frac{m}{d})\),因此可以知道 \((0, 0)\) 所在组的对角线集合就是从 \(x + y = 0\) 开始每 \(d\) 个间距分布的对角线。

推广到所有组,发现第 \(i\) 组就是 \(x + y = i + dx(0 \le x < \frac{n + m}{d})\).

因此这个问题只需要确定 \(x + y = 0 \sim d – 1\) 这 \(d\) 条对角线上是如何走的即可确定全图是怎么走的,也即确定前 \(d\) 步是怎么走的。

考虑前 \(d\) 步怎么走是合法的,当且仅当第一次遇到走过的点在恰好走了 \(nm\) 步以后。

首先我们发现:对于某条对角线上的点 \(x + y = k\) 一定要恰好走 \(n + m(d \mid (n + m))\) 步以后才能再次回到这条对角线,在此期间,一定走了若干次完整的周期,则:

  • 观察 2:第一次走到一个重复点时一定恰好走完了若干个整周期。
  • 观察 3:同一周期内,决定第一次走到重复点时刻的与周期内走的顺序无关,只与周期内往下 / 往右走的次数有关。

假设一个周期内往下走了 \(a\) 步,则根据裴蜀定理,在第一维走回来需要 \(\frac{n}{(n, a)}d\) 步,第二维类似地需要 \(\frac{m}{(m, d – a)}d\) 步,因此第一次走回来的时刻为:\(\mathrm{lcm}\left(\frac{n}{(n, a)}, \frac{m}{(m, d – a)}\right)d\),我们需要满足:

对此,我们考察 \(n, m\) 所包含的每个质因子 \(p\),令 \(\alpha_1 = \max_{p ^ i \mid n} i, \alpha_2 = \max_{p ^ i \mid m} i\)

  • 若 \(\min(\alpha_1, \alpha_2) = 0\).

若 \(p \mid (n, a)\) 则 \(\alpha_1 > 0\),可知等式左侧一定比右侧少了至少一个因子 \(p\),故 \(p \nmid (n, a)\),同理 \(p \nmid (m, d – a)\).

  • 若 \(\min(\alpha_1, \alpha_2) > 0\)

则 \(p \mid d\),若 \(p \mid (n, a)\) 则 \(p \mid a \Rightarrow p \mid (m, d – a)\) 故左侧两项均除去了至少一个 \(p\),一定比右式至少少了一个 \(p\).

同理可得 \(p \nmid (m, d – a)\)

综上,\(\forall p \mid n \lor p \mid m\) 总有 \(p \nmid (n, a), p \nmid (m, d – a)\) 故有上式成立的必要条件 \((n, a) = (m, d – a) = 1\)

而这显然也是充分条件,因此所有的方案数即:\(\sum\limits_{a} ^ d \binom{d}{a}[(n, a) = (m, d – a) = 1]\),考虑回到原问题。

首先枚举合法的 \(a\),对于每个 \((x, y)(x \le a, y \le d – a)\),其如果在第一周期走的路径内那么所有周期当中第 \(x + y + 1\) 步的位置都将随之确定,因此也可以确定这些位置当中最靠前的障碍的位置是在第几步,记作 \(w_{x, y}\).

于是有一个简单 \(\rm dp\),记 \(f_{i, j, k}\) 为第一周期当中,确定了前 \(i + j\) 步的走法,第 \(i + j\) 步在 \((i, j)\) 当前走到的所有位置中 \(w\) 的最小值为 \(k\) 的方案,转移显然,复杂度 \(\mathcal{O}(Tn ^ 5)\).

通过一定的常数优化已经可以通过了,但本题存在更优的解法。

既然是周期性移动,那么自然可以将碰到障碍的步数分解为:第几周期 + 第一周期内的第几步。

枚举最终碰到障碍步数在第 \(t\) 周期,求出 \(f_{i, j}\) 考虑完第一周期的前 \(i + j\) 步,第 \(i + j\) 步在 \((i, j)\),走到的每一个位置的 \(w\) 都至少在在第 \(t + 1\) 周期之后的方案,以及 \(g_{i, j}\) 为确定了第 \(i + j + 1 \sim d\) 步(走到 \((a, d – a)\))第 \(i + j + 1\) 前位置为 \((i, j)\),路径上的每个位置的 \(w\) 至少在第 \(t\) 周期之后的方案。

枚举在哪个位置第一次碰到障碍,利用 \(f, g\) 合并即可,复杂度 \(\mathcal{O}(Tn ^ 4)\).

————————

In this problem, for convenience, we change the coordinate range to \ ((0 \ SIM n – 1, 0 \ SIM m – 1) \), and walking can be regarded as any one dimension \ (+ 1 \) in the sense of module

At the same time, if you notice that a position can only pass through once, you can make \ (a {x, y} \) as \ ((x, y) \) whether the position goes downward or upward to facilitate investigation.

Firstly, the number of schemes of this problem is considered. For this kind of grid graph walking problem, it is generally necessary to investigate the special properties of diagonals.

  • Observe 1: \ (\ forall (x, y) \), if \ (a {(x – 1) \ bmod n, y} \ ne a_ {x, (Y – 1) \ bmod m} \), then either \ ((x, y) \) is passed twice or not.
  • (a \, a \ {, a \, a \, m \, OD = all) \ uy {, a \, a \, M:}

Investigating the combined representation of inference 1 is equivalent to dividing the whole grid graph into several groups. Each group is composed of several complete sub diagonals, and \ (a \) in each group is the same. Naturally, we can further consider the composition of diagonals in each group.

Copy and extend the grid graph to the left and right, and investigate the set composed of the sub diagonal at the beginning of the first line in the group where \ ((0, 0) \) is located at this time.

It is not difficult to find that it is \ (NX (x \ in \ mathbb {n}) \), which corresponds to the value of \ (nx \ bmod m (x \ in \ mathbb {n}) \) in the original grid diagram.

According to peishu theorem, this value must be \ (DX (d = (n, m), 0 \ Le X & lt; \Frac {m} {D}) \), so you can know that the diagonal set of the group in which \ ((0, 0) \) is distributed every \ (D \) spacing from \ (x + y = 0 \).

Extended to all groups, it is found that group \ (I \) is \ (x + y = I + DX (0 \ Le X & lt; \ frac {n + m} {D}) \)

Therefore, this problem only needs to determine how to walk on the diagonal line of \ (x + y = 0 \ SIM D – 1 \) to determine how to walk in the whole graph, that is, how to walk in the first \ (D \) step.

It is legal to consider how to take the first \ (D \) step, if and only if the first point encountered is just after the \ (nm \) step.

First of all, we find that for a point \ (x + y = k \) on a diagonal, we must just take \ (n + m (D \ mid (n + m)) \) steps before returning to the diagonal again. During this period, we must take several complete cycles, then:

  • Observation 2: when you reach a repetition point for the first time, you must have completed several whole cycles.
  • Observation 3: in the same cycle, the time determining the first time to go to the repetition point is not related to the order of going in the cycle, but only related to the number of going down / right in the cycle.

Assuming that \ (a \) steps are taken down in a cycle, according to Pei Shu’s theorem, it takes \ (\ frac {n} {(n, a)} D \) steps to walk back in the first dimension and \ (\ frac {m} {(m, D – A)} D \) steps similarly in the second dimension. Therefore, the first time to walk back is: \ (\ mathrm {LCM} \ left (\ frac {n} {(n, a)}, \ frac {m} (m, D – a)} \ right) d \), and we need to meet:

In this regard, we investigate each quality factor \ (P \) contained in \ (n, m \), so that \ (\ alpha_1 = \ max_{p ^ I \ mid n} I, \ alpha_2 = \ max_{p ^ I \ mid m} I \)

  • If \ (\ min (\ alpha_1, \ alpha_2) = 0 \)

If \ (P \ mid (n, a) \), then \ (\ alpha_1 & gt; 0 \), it can be seen that the left side of the equation must be less than the right side by at least one factor \ (P \), so \ (P \ nmid (n, a) \), similarly \ (P \ nmid (m, D – a) \)

  • If \ (\ min (\ alpha_1, \ alpha_2) > 0 \)

Then \ (P \ mid D \), if \ (P \ mid (n, a) \), then \ (P \ mid a \ rightarrow P \ mid (m, D – a) \), so at least one \ (P \) is removed from both items on the left, which must be at least one \ (P \) less than the right

Similarly \ (P \ nmid (m, D – a) \)

To sum up, \ (\ forall P \ mid n \ lor P \ mid m \) always has \ (P \ nmid (n, a), P \ nmid (m, D – a) \), so there is a necessary condition for the above formula to hold \ ((n, a) = (m, D – a) = 1 \)

This is obviously a sufficient condition, so all the schemes, i.e. \ (\ sum \ limits {a} ^ D \ binom {D} {a}[(n, a) = (m, D – a) = 1] \), are considered to return to the original problem.

Firstly, enumerate the legal \ (a \). For each \ ((x, y) (x \ Le a, y \ le d – a) \), if it is within the path of the first cycle, the position of step \ (x + y + 1 \) in all cycles will be determined accordingly. Therefore, it can also be determined that the position of the most front obstacle in these positions is in step \ (w_{x, y} \)

Therefore, there is a simple scheme in which \ (\ RM DP \) is recorded as \ (f {I, J, K} \) in the first cycle, which determines the walking method of the first \ (I + J \) step, and the minimum value of \ (w \) in all the positions currently reached by \ ((I, J) \) in step \ (\ mathcal {o} (TN ^ 5) \)

Through a certain constant optimization, it can be passed, but there is a better solution to this problem.

Since it is a periodic movement, it is natural to decompose the steps that encounter obstacles into: the number of cycles + the number of steps in the first cycle.

Enumerate the number of steps that finally encounter obstacles in the \ (t \) cycle, and find the scheme that \ (f_{i, J} \) considers the first \ (I + J \) step of the first cycle, the \ (I + J \) step is \ ((I, J) \), and the \ (w \) at each position is at least after the \ (T + 1 \) cycle, And \ (g_{i, J} \) is the scheme that determines that in step \ (I + j + 1 \ SIM D \) (the position before going to \ ((a, D – a) \) (I + j + 1 \) is \ ((I, J) \), and the \ (w \) of each position on the path is at least after the \ (t \) cycle.

Enumerate where obstacles are encountered for the first time, and use \ (F, G \) to merge. Complexity \ (\ mathcal {o} (TN ^ 4) \)