牛客 26 多校 2 - Imperfect Dot Sums and Cross Sums

2026/7/23 3:05:27

2026 牛客暑期多校 2 - I - Imperfect Dot Sums and Cross Sums

给定了 $n \le 10^5$ 个随机的三维向量 $V_i = (x_i, y_i, z_i)$，值域在 $\pm 10^6$ 范围。

有 $q \le 10^5$ 次询问，每次询问给出一个区间 $[L,R]$，以及一个随机的三维向量 $T$。

你需要回答 $\sum_{i=l}^r (\vert{}V_i \cdot T\vert{} + \Vert{}V_i \times T\Vert{})$ 的值，只要误差在 $10\%$ 以内即可接受。

PS. 这个式子是指点积的绝对值 + 叉积的模长。

观察每个单项 $v_i = (\vert{}V_i \cdot T\vert{} + \Vert{}V_i \times T\Vert{})$，那么:

点积的绝对值：$\vert{}V_i \cdot T\vert{} = \Vert{}V_i\Vert{} \Vert{}T\Vert{} \vert{}\cos \theta_i\vert{}$
叉积的模长：$\Vert{}V_i \times T\Vert{} = \Vert{}V_i\Vert{} \Vert{}T\Vert{} \sin \theta_i$

提取公因式就是 $v_i = \Vert{}V_i\Vert{} \Vert{}T\Vert{} (\vert{}\cos \theta_i\vert{} + \sin \theta_i)$，同时注意后半部分 $f(\theta_i) \in [1, \sqrt 2]$

Sol1 蒙特卡洛

首先有一个很 naive 的做法，随机区间中的 $B$ 个向量计算贡献，取平均值，再乘区间长度。
不过由于区间里模长的分布是不平均的，这样做的方差太大，是无法满足精度的要求的。

考虑这个事实，如果一个向量的模长 $\Vert{}V\Vert{}$ 越大，它对答案的贡献就越大。

我们可以通过加权，调整每个向量被随机到的概率 $p_i = {\Vert{}V\Vert{} \over W}$，这里 $W$ 是区间所有模长之和。

此时单次采样的估计量是

\[Y= \frac{v_i}{p_i} = W \Vert{}V\Vert{} f(\theta_i) \]

也就是说估计量 $Y$ 被限制在了 $W\Vert{}T\Vert{}$ 到 $1.414 W\Vert{}T\Vert{}$ 之间，单次相对标准差不超过 $20\%$。

我们重复 $B = 100$ 次采样，相对误差就到了 $\frac{20\%}{\sqrt B} = 2\%$，完全够用，加权平均后即可通过 Link。

Sol2-1 离线 $\epsilon$-聚类

官方 std 的做法（感觉比较一般吧，但是也很有启发）

我们先离线所有询问，取一个询问向量 $T$，将与其夹角小于 $\epsilon$ 的全部打包为一组。

假设这组询问向量都是一样的，在$O(n)$ 预处理前缀和以后，可以 $O(1)$ 回答每个询问。

正确性比较显然，因为这一组的 $f(\theta_i)$ 都比较接近，误差不会太大。

STD 说期望会进行 $O(\log^2 \epsilon)$ 轮，故复杂度为 $O(n+q) \log^2 \epsilon$。

我怎么感觉是会进行 $O(\epsilon ^ {-2})$ 轮，总复杂度为 $O(n \epsilon ^ {-2})$ 呢，代码应该很难写...

关于为什么认为是 $O(\epsilon ^ {-2})$

打包相当于射出了一个半角为 $O(\epsilon)$ 的圆锥，投影到单位球面的表面积为 $2 \pi (1 - \cos \epsilon)$。

由于 eps 应该是不太大的，泰勒展开 $\cos \epsilon \approx 1 - \frac{\epsilon^2}{2} $

代入表面积公式得到每次覆盖的球表面积大致是 $\pi \epsilon^2$，期望轮次为 $\frac{4\pi}{\epsilon^2} = O(1/\epsilon^2)$

当心夹脚

Sol2-2 球面分块

既然可以把询问打包，无视它们的角度差异，我们当然可以反过来把序列上的向量打包。

可以按极角和方位角进行划分出 $20 \times 30 = 600$ 个网格，并算出每个网格正中心的标准向量。

接下来我们为了回答区间询问，不妨再对序列进行分块，具体的做法是做一个二维前缀和：

维护 $dp[b][m]$ 表示在前 $m$ 个块中，第 $b$ 个网格里的向量模长之和。
假设块内所有模长都是集中在标准向量上的。

查询对散块暴力，再枚举每个网格 $O(1)$ 查询整块的贡献，这样是 $O((n + q) \sqrt n)$ 了。

别人的代码 link，太美丽了这个做法。

Sol3 多项式拟合

不知道大家有没有参加过算子比赛，一个常用手法是用低次多项式逼近复杂函数，在精度误差范围内加速。

我们令 $y = \cos^2 \theta_i$，那么

\[v_i = \Vert{}V_i\Vert{} \Vert{}T\Vert{} (\sqrt{y} + \sqrt{1 - y}) \]

可以用切比雪夫逼近找到 $P(y) = 1.0675 + 1.25 y - 1.25y^2$ 替换 $\sqrt{y} + \sqrt{1 - y}$。

可以验证 $P(y)$ 的精度，在 $[0, 1]$ 内最大误差为 $6.75\%$，满足题目要求。

在多项式替换后，我们将 $y = \cos^2 \theta_i = \frac{(V_i \cdot T)^2}{\Vert{}V_i\Vert{}^2 \Vert{}T\Vert{}^2}$ 代回原方程：

\[v_i \approx 1.0675 \Vert{}T\Vert{} \cdot \Vert{}V_i\Vert{} + \frac{1.25}{\Vert{}T\Vert{}} \cdot \frac{(V_i \cdot T)^2}{\Vert{}V_i\Vert{}} - \frac{1.25}{\Vert{}T\Vert{}^3} \cdot \frac{(V_i \cdot T)^4}{\Vert{}V_i\Vert{}^3} \]

把 $T$ 提出来以后，提前对所有 $V_i$ 相关的 $0,2,4$ 次项分别维护 $1,6,15$ 共 $22$ 个前缀和。

即可在 $O(1)$ 时间里回答每个询问，预处理写起来比较吃技巧 link，跑得飞快 500ms。