AT_jsc2022_final_e Circular Sushi 题解

zrl123456 · 2026-03-04 21:58:49 · 题解

:::::info[题目基本信息] 考察：扩展欧几里得算法，数论，字典树 Trie。

题目简介：
有一个长度为 2^m 的圆环，点的坐标可以取属于 [0,2^m) 的任意实数。
现在上面有 n 个点在移动，第 i 个点的初始坐标为整数 a_i，并以每秒 b_i 单位长度的速度向坐标更大的方向移动，权值为 c_i。
现在你可以选择一个非负实数 t，定义你的得分为此时位于坐标为 0 的所有点的权值和，求你的得分的最大值。

数据范围：

1\le n\le 2\times 10^5
1\le m\le 30
\forall i\in[1,n],0\le a_i<2^m
\forall i\in[1,n],1\le b_i<2^m
\forall i\in[1,n],1\le c_i\le 10^9

时空限制：

时间限制：4s。
空间限制：1GB。 ::::: :::::success[Hint] ::::info[Hint 1] 对于每一个 i 分别考虑，列出 t 满足的关系式，考虑转化为可做形式。 :::: ::::info[Hint 2] 考虑缩小最优解 t 的范围，直到范围可以满足转化关系式的需求。 :::: ::::info[Hint 3] 观察题目中所给的参量，有没有有特殊性质的量？和 t 的范围是否有关系？ :::: ::::info[Hint 4] 列出最终的关系式后考虑其本质，考虑使用数据结构快速维护。 :::: ::::: 对于任意 i，考虑列式推导第 i 点在坐标为 0 的点上时 t 需要满足的关系式，先列出最显然的式子： a_i+b_it\equiv 0\pmod{2^m}
由于 t 是实数，所以同余方程不能直接解，考虑将其转化为整数。

显然 t 是有理数，否则这些点连整点都到不了。
设 t=\frac{p}{q}，我们想要将方程转化成全整数可以同乘一个数，那么要求这个数必须是 q 的倍数，但是显然 q 的可能性太多 \text{lcm} 太大不能直接乘，考虑最优解的 t 可能是什么样子。
遇到 \text{lcm} 自然想到将 p 和 q 质因数分解，我们要求 \text{lcm} 量级可控自然要消去 q 的部分质因子。考虑这个题的环长很特殊，是 2 的幂次，考虑能不能只保留 2。
取 q 除 2 以外的其它质因子的乘积 r，考虑将这个 q 转化为另一不含 2 以外质因子的 q' 的最简单的方式就是将 r 转化 1。
注意到 r 和 2^m 互质，即最大公约数是 1，根据我们要代入同余方程的目的，联想到裴蜀定理，列出方程 2^mx+ry=1，也就是 r\,|\,2^mx-1，那么令 t'=(2^mx-1)t，那么我们得到：

\begin{aligned}a_i+b_it'\equiv 0\pmod {2^m}&\Leftrightarrow a_i+b_i(2^mx-1)t\equiv 0\pmod {2^m}\\&\Leftrightarrow a_i-b_it\equiv 0\pmod {2^m}\end{aligned}

虽然和预想中不太一致，但是我们注意到只需要将上一段的方程改写为 2^m+ry=-1 最终得到的结果就是我们的预期了，就这样我们成功地将 q 限制为了 2 的幂次。

那么这时我们在同余方程同乘 2^m 即可，令 T=2^mt，那么我们得到：

a_i2^m+b_iT\equiv 0\pmod {2^{2m}}

移项过去容易得到：

b_iT\equiv-a_i2^m\pmod{2^{2m}}

令 b_i=2^db'_i（b'_i 为奇数），替换得到：

2^db'_iT\equiv-a_i2^m\pmod {2^{2m}}

同除以 2^d，得到：

b'_iT\equiv-a_i2^{m-d}\pmod{2^{2m-d}}

注意到 b'_i 相对于 2^{2m-d} 右逆元，那么我们令 b'_iw\equiv -a_i\pmod{2^m}，我们得到：

T\equiv w2^{m-d}\pmod{2^{2m-d}}

我们考虑这个东西的实质，实际上是限制了 T 的一段二进制表示下的后缀，那么我们考虑建立 Trie 树（最低位离根最近），容易求出最终的答案。

这样我们就做完了这道题。
时空复杂度均为 \Theta(n\log V)。