自动搬运

查看原文

来自洛谷，原作者为

	jimmywang 基环内向树，二维前缀和，三碳化四铝，闪电五连鞭

搬运于2025-08-24 23:12:46，当前版本为作者最后更新于2025-01-05 19:15:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

远没有 2900。

显而易见的，这个题需要我们找到循环节内，两个矩形相交的次数。

众所周知，两条线段相交的判定为 $\text{intersect}(\ (l_1,r_1),(l_2,r_2)\ )=[\max(l_1,l_2)\le \min(r_1,r_2)]$。

众所周知，两个矩形 $(\ (x_1,y_1),(x_2,y_2)\ ),(\ (x_3,y_3),(x_4,y_4)\ )$（表示方法为左上坐标和右下坐标）相交的判定为 $\text{intersect}(\ (x_1,x_2),(x_3,x_4)\ )\times\text{intersect}(\ (y_1,y_2),(y_3,y_4)\ ) $。

我们把 $x,y$ 两个维度分开考虑。

一个矩形在 $x$ 轴方向的循环节是 $2(W-w)$，那么两个矩形的公共循环节就是 $L_x=\operatorname{lcm}(2(W-w_1),2(W-w_2))\le 4W^2\le6.4\times 10^7$。

我们暴力枚举 $time\in[0,L_x)$ 并模拟这两个矩形的运动，每次 $O(1)$ 得到这两个矩形的 $\text{intersect}(\ (x_1,x_2),(x_3,x_4)\ )$ ，于是我们得到了一个长度为 $L_x$ 的 01 串 $X$。

对 $y$ 轴方向同理，得到长度为 $L_y=\operatorname{lcm}(2(H-h_1),2(H-h_2))$ 的 01 串 $Y$。

众所周知，总循环节应该是 $L=\operatorname{lcm}(L_x,L_y)$，同样这应该是最终答案（化简前）的分母，分子是 $\sum_{i=0}^{L-1}[X_{i \bmod L_x}=1][Y_{i\bmod L_y}=1]$。现在的困难在于求出这个玩意。

换个方式，我们枚举 $X_i=1$ 的 $i$ 和 $Y_j=1$ 的 $j$。那么就是

$$\sum_{i}\sum_{j}(\text{\# of T, such that } T\equiv i \pmod {L_x},T\equiv j \pmod {L_y}) $$

熟悉 exCRT 的人一眼丁真这玩意有解当且仅当 $\gcd(L_x,L_y)\mid (i-j)$，且 $T=T^*+k\operatorname{lcm}(L_x,L_y)=T^*+kL$，其中 $T^*$ 是一个特解。后者相当于告诉我们 $[0,L)$ 范围内要么有唯一解，要么无解；前者等价于 $i \equiv j \pmod{\gcd(L_x,L_y)}$。

于是我们再次转换枚举的东西，因为同余，所以我们枚举余数。设这个 $\gcd(L_x,L_y)=g \le \min(L_x,L_y)\le 6.4\times 10^7$。

$$\begin{aligned}&=\sum_{d=0}^{g-1}\sum_{i}[X_i=1][i \bmod g = d]\sum_{j}[Y_j=1][j \bmod g = d]\\&=\sum_{d=0}^{g-1}(\sum_{i}[X_i=1][i \bmod g = d])(\sum_{j}[Y_j=1][j \bmod g = d])\end{aligned} $$

这两个括号内的东西都能通过扫一遍 $X$ 或 $Y$ 得到。

于是做完了。复杂度 $O(H^2)$（$H,W$ 同阶）。