CF2052 (NERC 2024Final) L Legacy Screensaver

· · 题解

远没有 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 同阶）。