2024第一学期 #9

T1.P10136

神秘人类智慧题。

如果离散化后的 \(n \le 3\)，那么答案即为 \(\dfrac{mx \times (mx + 1)}{2}\)。接下来考虑 \(n \ge 4\) 的情况。

应为鸽巢原理当 \(a_i \bmod L\) 只有三种不同的取值，所以必定有两个数 \(i,j\) 满足条件 \(a_i \equiv a_j \pmod L\) 并且 \(1 \le i < j \le 4\)。那么就可以推出 \(L \mid (a_i-a_j)\)。

那么我们只需要枚举所有满足条件 \(1 \le i < j \le 4\) 的 \(i,j\)，然后查看 \(a_i - a_j\) 的所有因数当中所有符合条件的数的和即可。

T2.P4156

我们先求出所有 \(|s| - \text{border}\) 的长度，记为 \(\{x_i\}\)，那么题目要求的就是 \(\sum^{cnt}_{i = 1} a_i \times x_i\) 能在 \([0,w - |s|]\) 中取到多少种值。

注意到这个形式是同余最短路的形式，所以我们考虑使用同余最短路来解决。但是直接做是 \(\mathrm O(n^2 \log n)\) 的，不可以通过。

此时抛出一个定理：一个字符串排序之后，必定有一种划分序列的方式，使得所有的序列均为等差序列，且序列个数为 \(\mathrm O( \log |s|)\)。

那么根据 \(\text{border}\) 这个优美的性质，我们考虑把 \(x,x + d,x + 2d \cdots \cdots x + l \times d\) 这个等差数列在 \(\bmod x\) 的意义下跑同余最短路。其中 \(y\) 连向 \((y + d) \bmod x\)。那么会形成 \(\gcd(x,d)\) 个环，每一个环分开处理。

我们发现一个环中 \(dis\) 最小的点是不会更新的。并且两边的点的 \(dis\) 均等于 \(d\)。那么我们就从这个点出发用单调队列结算 \(dis\)。我们在单调队列里放入离现在处理点距离小于等于 \(l\) 的点，以 \(dis_i - pos_i \times d\) 作为比较，这样我们就能处理环上的转移。

那么剩下的为题就是怎么两个不模数的转移。假设现在的模数为 \(now\)，之前的为 \(lst\)，那么很明显 \(dis_i\) 可以更新 \(dis^{'}_{dis_i \bmod now}\)。然后根据定义我们只需要在 \(\bmod now\) 的意义下跑一遍同余最短路并且使用用 \(x\) 更新 \((x + lst) \bmod now\) 即可。

时间复杂度为 \(\mathrm O(n \log n)\)。