「三重求和」题解

问题分析

给定序列 $a_1, \dots, a_n$，对于每个询问 $(d, p_1, p_2)$，计算：

$$S = \sum_{i=0}^{d-1} \sum_{j=0}^{d-1} \sum_{k=0}^{d-1} a_{p_1+d\cdot i+j} \cdot a_{p_2 + d\cdot j + k} $$

其中 $0 \leq i,j,k < d$，需要保证下标在 $[1, n]$ 范围内。

表达式分析

1. 下标分析

设：

• $X = p_1 + d\cdot i + j$
• $Y = p_2 + d\cdot j + k$

其中：

• $i,j,k$ 各自独立地从 $0$ 到 $d-1$
• $X$ 依赖于 $i$ 和 $j$
• $Y$ 依赖于 $j$ 和 $k$

2. 重写求和式

$$S = \sum_{j=0}^{d-1} \left( \sum_{i=0}^{d-1} a_{p_1+d\cdot i+j} \right) \cdot \left( \sum_{k=0}^{d-1} a_{p_2 + d\cdot j + k} \right) $$

令：

• $A_j = \sum_{i=0}^{d-1} a_{p_1+d\cdot i+j}$，其中 $0 \leq j < d$
• $B_j = \sum_{k=0}^{d-1} a_{p_2 + d\cdot j + k}$，其中 $0 \leq j < d$

则：

$$S = \sum_{j=0}^{d-1} A_j \cdot B_j$$

3. 几何解释

$A_j$ 是从位置 $p_1+j$ 开始，步长为 $d$ 的 $d$ 个元素之和。 $B_j$ 是从位置 $p_2+d\cdot j$ 开始，连续的 $d$ 个元素之和。

具体来说：

• $A_j$：在序列 $a$ 中，取位置 $p_1+j, p_1+j+d, p_1+j+2d, \dots, p_1+j+(d-1)d$ 共 $d$ 个元素求和
• $B_j$：在序列 $a$ 中，取位置 $p_2+d\cdot j, p_2+d\cdot j+1, p_2+d\cdot j+2, \dots, p_2+d\cdot j+(d-1)$ 共 $d$ 个元素求和

算法思路

暴力方法（不可行）

直接按照公式计算：

• 对每个询问，计算 $A_j$ 和 $B_j$ 各需要 $O(d^2)$ 时间（因为每个 $A_j$ 需要求 $d$ 个元素的和）
• 总复杂度 $O(m \cdot d^2)$，最坏 $O(m \cdot n^2)$，不可行

优化方向

我们需要预处理一些信息，使得能够快速计算 $A_j$ 和 $B_j$。

优化 $A_j$ 的计算

$A_j = \sum_{i=0}^{d-1} a_{p_1+d\cdot i+j}$

对于固定的 $d$ 和 $p_1$，$A_j$ 是 $j$ 的函数。这可以看作在模 $d$ 意义下的分组求和。

定义序列 $b_t = a_{p_1+t}$（重新编号，从0开始），则：

$$A_j = \sum_{i=0}^{d-1} b_{j + d\cdot i} = \sum_{i: i \equiv j \ (\text{mod } d)} b_i $$

即 $A_j$ 是 $b$ 序列中所有模 $d$ 余 $j$ 的位置的和。

优化 $B_j$ 的计算

$B_j = \sum_{k=0}^{d-1} a_{p_2 + d\cdot j + k}$

这是连续的 $d$ 个元素的和，可以使用前缀和优化：

设 $pre[i] = \sum_{t=1}^i a_t$，则：

$$B_j = pre[p_2 + d\cdot j + d - 1] - pre[p_2 + d\cdot j - 1] $$

前提是下标在范围内。

预处理策略

对 $A_j$ 的预处理

对于每个可能的模数 $d$，我们需要快速查询：从位置 $p_1$ 开始，所有模 $d$ 余 $j$ 的位置的和。

设 $f(d, r, start, len)$ 表示从位置 $start$ 开始，长度为 $len$ 的范围内，所有模 $d$ 余 $r$ 的位置的元素和。

但由于 $d$ 最多可达 $n$，无法为所有 $d$ 预处理。

根号分治

使用根号分治策略：

• 对于小的 $d$（$d \leq \sqrt{n}$）：预处理所有可能的信息
• 对于大的 $d$（$d > \sqrt{n}$）：直接暴力计算，因为此时循环次数 $d$ 较小

设阈值 $B = \sqrt{n} \approx 450$（因为 $n \leq 2\times 10^5$）。

小 $d$ 的情况（$d \leq B$）

预处理数组 $sum[d][r][t]$ 表示：前 $t$ 个位置中，所有模 $d$ 余 $r$ 的元素之和。

那么：

$$A_j = sum[d][j][p_1 + (d-1)d + j] - sum[d][j][p_1 - 1] $$

但注意：我们只需要从 $p_1$ 开始，每隔 $d$ 取一个元素，共取 $d$ 个。

更精确地说：$A_j$ 是从 $p_1+j$ 开始，每隔 $d$ 取一个，取 $d$ 次。

可以预处理 $g[d][r][k]$ 表示从位置 $r$ 开始，每隔 $d$ 取一个，取 $k$ 个的和。但这样空间太大。

更好的方法：对于每个小 $d$，我们预处理一个前缀和数组 $pre_{d}[i]$，表示前 $i$ 个位置中，所有模 $d$ 余 $0$ 的元素之和，余 $1$ 的元素之和，...，余 $d-1$ 的元素之和。

但 $d$ 最多 $B$，每个 $d$ 需要 $n$ 个位置，每个位置存储 $d$ 个余数的和，总空间 $O(B^2 \cdot n)$，太大。

实际上，我们可以只存储每个余数的前缀和：$sum[d][r][i]$ 表示前 $i$ 个位置中模 $d$ 余 $r$ 的元素之和。

空间：$O(\sum_{d=1}^B d \cdot n) = O(B^2 \cdot n) = O(n^{1.5} \cdot n) = O(n^{2.5})$，还是太大。

需要进一步优化。

改进的小 $d$ 预处理

注意到 $A_j$ 需要的是从特定位置开始，每隔 $d$ 取一个的和，而不是所有模 $d$ 余 $j$ 的和。

我们可以预处理另一种结构：对于每个 $d$，将序列分成 $d$ 个等差数列，然后对每个等差数列预处理前缀和。

具体来说：

• 对于模 $d$ 余 $r$ 的位置：$r, r+d, r+2d, \dots$
• 对这些位置建立前缀和数组 $prefix[d][r][k]$，表示前 $k$ 个这样的元素的和

那么 $A_j$ 就是从 $p_1+j$ 开始（这是第 $t$ 个这样的元素），取 $d$ 个连续元素的和。

空间：每个 $d$ 有 $d$ 个等差数列，每个数列长度约 $n/d$，总空间 $O(\sum_{d=1}^B d \cdot (n/d)) = O(B \cdot n) = O(n^{1.5})$，可接受。

大 $d$ 的情况（$d > B$）

此时 $d$ 较大，但 $d$ 的上限是多少？由于 $p_1 + d\cdot (d-1) + (d-1) \leq n$，所以 $d^2 \leq n$，即 $d \leq \sqrt{n}$。

等等，检查一下：$X = p_1 + d\cdot i + j$ 最大是 $p_1 + d\cdot (d-1) + (d-1) = p_1 + d^2 - 1 \leq n$，所以确实 $d^2 \leq n$。

因此 $d \leq \sqrt{n} \approx 447$，这与我们的阈值 $B$ 相同！

这意味着所有询问的 $d$ 都满足 $d \leq \sqrt{n}$！

重要发现：由于下标限制 $p_1 + d^2 - 1 \leq n$，所以 $d \leq \sqrt{n}$。

因此所有询问的 $d$ 都是"小"的，我们可以直接使用小 $d$ 的预处理方法。

最终算法

预处理

设 $B = \lfloor \sqrt{n} \rfloor$

对于每个 $d = 1$ 到 $B$：

1. 将序列分成 $d$ 个等差数列：对于 $r = 0$ 到 $d-1$，位置为 $r, r+d, r+2d, \dots$
2. 对每个等差数列建立前缀和数组 $pre[d][r][k]$，其中 $pre[d][r][k]$ 表示该等差数列前 $k$ 个元素的和

具体实现：对于每个 $d$，我们有 $d$ 个数组，每个数组长度约为 $n/d$。

查询计算

对于询问 $(d, p_1, p_2)$：

1. 计算 $A_j$（$0 \leq j < d$）

对于每个 $j$，$A_j$ 是等差数列 $j, j+d, j+2d, \dots$ 中从某个位置开始的连续 $d$ 个元素的和。

从哪个位置开始？我们需要找到 $p_1+j$ 在这个等差数列中是第几个元素。

设等差数列为：$j, j+d, j+2d, \dots$ 元素 $p_1+j$ 在这个数列中的索引为：$t = \frac{(p_1+j) - j}{d} = \frac{p_1}{d}$？不对，$p_1+j$ 可能不是等差数列的起点。

实际上，等差数列的第一个元素是某个 $r$ 满足 $r \equiv j \ (\text{mod } d)$，且 $r \leq j$。更简单的方法：

等差数列中的第 $k$ 个元素是 $j + (k-1)d$。

我们需要找到最小的 $k$ 使得 $j + (k-1)d \geq p_1+j$，即 $(k-1)d \geq p_1$，所以 $k = \lceil p_1/d \rceil + 1$？

实际上更简单：我们要求的是从 $p_1+j$ 开始（包含），每隔 $d$ 取一个，取 $d$ 个。

设 $start = p_1+j$，那么取的序列是：$start, start+d, start+2d, \dots, start+(d-1)d$

这些元素在等差数列 $j, j+d, j+2d, \dots$ 中的索引：

第一个元素 $start$ 在等差数列中的索引：$t_1 = \frac{start - j}{d} = \frac{p_1+j - j}{d} = \frac{p_1}{d}$

最后一个元素 $start+(d-1)d$ 的索引：$t_2 = \frac{p_1+j+(d-1)d - j}{d} = \frac{p_1}{d} + (d-1)$

所以 $A_j = pre[d][j][t_2+1] - pre[d][j][t_1]$，使用前缀和计算。

2. 计算 $B_j$（$0 \leq j < d$）

$B_j = \sum_{k=0}^{d-1} a_{p_2 + d\cdot j + k}$

这是连续 $d$ 个元素的和，使用普通的前缀和：

$$B_j = pre\_global[p_2 + d\cdot j + d - 1] - pre\_global[p_2 + d\cdot j - 1] $$

其中 $pre\_global[i] = \sum_{t=1}^i a_t$ 是全局前缀和。

3. 计算答案

$$S = \sum_{j=0}^{d-1} A_j \cdot B_j$$

需要模 $2^{32}$，可以使用 unsigned int 自动取模。

复杂度分析

预处理

• 对于每个 $d$，需要处理 $d$ 个等差数列
• 每个等差数列平均长度 $n/d$
• 总元素数：$\sum_{d=1}^B d \cdot (n/d) = B \cdot n = O(n^{1.5})$
• 预处理复杂度：$O(n^{1.5})$

查询

• 对于每个询问，需要计算 $d$ 个 $A_j$ 和 $d$ 个 $B_j$
• 每个 $A_j$ 需要 $O(1)$ 时间（通过预处理的等差数列前缀和）
• 每个 $B_j$ 需要 $O(1)$ 时间（通过全局前缀和）
• 计算点积需要 $O(d)$ 时间
• 总查询复杂度：$O(\sum_{i=1}^m d_i)$

由于 $d_i \leq \sqrt{n}$，总复杂度 $O(m\sqrt{n})$，对于 $m=2\times 10^5$，最坏 $2\times 10^5 \times 447 \approx 9\times 10^7$，可接受。

实现细节

1. 数据结构

• pre_global[i]：全局前缀和
• 对于小 $d$ 的预处理：使用二维向量或数组存储 pre[d][r][k]
  • 第一维：$d$（1到$B$）
  • 第二维：余数 $r$（0到$d-1$）
  • 第三维：前缀和索引

2. 内存优化

由于 $B \approx 447$，$d$ 的最大值是447。 对于每个 $d$，需要存储 $d$ 个数组。 总元素数大约 $447 \times n = 447 \times 2\times 10^5 \approx 9\times 10^7$ 个整数。 每个整数4字节，约360MB，可能太大。

需要进一步优化内存：

优化方案：

1. 不存储所有 $d$ 的预处理信息，只存储 $d$ 较小的部分
2. 或者，对于每个 $d$，我们不需要存储所有余数的前缀和，只需要在查询时临时计算

实际上，计算 $A_j$ 也可以通过另一种方式：$A_j$ 就是从 $p_1+j$ 开始，每隔 $d$ 取一个，取 $d$ 个。我们可以直接计算这 $d$ 个元素的和，每个元素用全局前缀和快速获取。

3. 简化实现

由于 $d \leq \sqrt{n}$，我们可以直接暴力计算 $A_j$：

对于每个 $j$：

$$A_j = \sum_{i=0}^{d-1} a_{p_1+d\cdot i+j}$$

这需要 $O(d)$ 时间计算一个 $A_j$，总共 $O(d^2)$ 时间计算所有 $A_j$。

而 $d^2 \leq n$，所以 $O(d^2) \leq O(n)$。

对于 $B_j$，使用全局前缀和 $O(1)$ 计算。

总查询复杂度：$O(m \cdot n)$？不对，是 $O(\sum d^2)$。

最坏情况：$m=2\times 10^5$，每个 $d=\sqrt{n}\approx447$，$d^2\approx2\times 10^5$，总 $2\times 10^5 \times 2\times 10^5 = 4\times 10^{10}$，太大。

4. 折中方案

使用阈值 $T$：

• 当 $d \leq T$ 时，使用预处理方法
• 当 $d > T$ 时，直接暴力计算 $A_j$（此时 $d$ 较小，$d^2$ 也较小）

设 $T = n^{2/3} \approx 3400$（对于 $n=2\times 10^5$），但 $d$ 最大只有447，所以所有 $d$ 都小于 $T$。

总结

最终算法：

1. 预处理全局前缀和
2. 对于 $d=1$ 到 $\sqrt{n}$，预处理每个等差数列的前缀和
3. 对于每个询问：
   • 用 $O(1)$ 时间计算每个 $B_j$（全局前缀和）
   • 用 $O(1)$ 时间计算每个 $A_j$（等差数列前缀和）
   • 计算点积 $S = \sum_{j=0}^{d-1} A_j \cdot B_j$

复杂度：

• 预处理：$O(n^{1.5})$
• 查询：$O(m \cdot \sqrt{n})$

对于 $n=2\times 10^5$，$n^{1.5} \approx 9\times 10^7$，$m\sqrt{n} \approx 9\times 10^7$，均可接受。

关键优化是发现 $d \leq \sqrt{n}$ 的约束，从而可以使用根号分治策略。